{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T21:08:47Z","timestamp":1672434527223},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["Br835\/15-1 and Br835\/15-2"],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2012,7]]},"abstract":"Directed graphs are commonly drawn by the Sugiyama algorithm where first vertices are placed on distinct hierarchical levels, and second vertices on the same level are permuted to reduce the overall number of crossings. Separating these two phases simplifies the algorithms but diminishes the quality of the result.<\/jats:p>\n We introduce a combined leveling and crossing reduction algorithm based on sifting, which prioritizes few crossings over few levels. It avoids type 2 conflicts, which are crossings of edges whose endpoints are dummy vertices. This helps straightening long edges spanning many levels. The obtained running time is roughly quadratic in the size of the input graph and independent of dummy vertices.<\/jats:p>","DOI":"10.1145\/2133803.2345682","type":"journal-article","created":{"date-parts":[[2012,10,16]],"date-time":"2012-10-16T12:50:57Z","timestamp":1350391857000},"source":"Crossref","is-referenced-by-count":2,"title":["Grid sifting"],"prefix":"10.1145","volume":"17","author":[{"given":"Christian","family":"Bachmaier","sequence":"first","affiliation":[{"name":"University of Passau, Passau, Germany"}]},{"given":"Wolfgang","family":"Brunner","sequence":"additional","affiliation":[{"name":"University of Passau, Passau, Germany"}]},{"given":"Andreas","family":"Glei\u00dfner","sequence":"additional","affiliation":[{"name":"University of Passau, Passau, Germany"}]}],"member":"320","published-online":{"date-parts":[[2012,10,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00242"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25878-7_42"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31843-9_52"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00088"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30559-0_28"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/647553.729421"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1671970.1671975"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00220"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288685"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(96)00005-3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187020"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/647554.729569"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.221135"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/647549.728900"},{"key":"e_1_2_1_15_1","volume-title":"Drawing Graphs. Lecture Notes in Computer Science","volume":"2025","author":"Kaufmann M."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-006-4296-7"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(96)00083-4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46648-7_22"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-25978-7_49"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/259794.259802"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1981.4308636"},{"key":"e_1_2_1_22_1","volume-title":"Proceeding of the International Conference on Imaging Science, Systems, and Technology (CISST'98)","author":"Utech J."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.2307\/3001968"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2133803.2345682","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T19:32:56Z","timestamp":1672342376000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2133803.2345682"}},"subtitle":["Leveling and crossing reduction"],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":23,"alternative-id":["10.1145\/2133803.2345682"],"URL":"https:\/\/doi.org\/10.1145\/2133803.2345682","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}