{"ID":6138065,"CreatedAt":"2026-07-09T01:07:32.349475501Z","UpdatedAt":"2026-07-11T03:40:41.502488863Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.06968","arxiv_id":"2607.06968","title":"Layer-Respecting Linear Graph Layouts","abstract":"We show how to visualize a graph, $G=(V,E)$, as a layered drawing, layer-respecting arc diagram, or layer-respecting linear cylindric drawing with a minimum number of edge crossings, where layer-respecting means that layers appear in order on a single line and vertices are grouped by their layers. Even though this problem is NP-hard for general arc diagrams, we show how to create such diagrams with fixed-parameter tractable linear-time algorithms, where the parameter that allows this is the width of a layered graph. Such a layered graph can be obtained from a breadth-first search (BFS), in which case the width is upper bounded by a graph width parameter called the BFS width.","short_abstract":"We show how to visualize a graph, $G=(V,E)$, as a layered drawing, layer-respecting arc diagram, or layer-respecting linear cylindric drawing with a minimum number of edge crossings, where layer-respecting means that layers appear in order on a single line and vertices are grouped by their layers. Even though this prob...","url_abs":"https://arxiv.org/abs/2607.06968","url_pdf":"https://arxiv.org/pdf/2607.06968v1","authors":"[\"Alvin Chiu\",\"David Eppstein\",\"Michael T. Goodrich\",\"Songyu Liu\"]","published":"2026-07-08T03:45:47Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}