Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs

DOI10.1016/j.comgeo.2015.07.002zbMath1332.05099arXiv1308.6706OpenAlexW2160179167WikidataQ62046547 ScholiaQ62046547MaRDI QIDQ904086

Fabrizio Montecchiani, Maurizio Patrignani, Luca Grilli, Walter Didimo, Carla Binucci, Giordano Da Lozzo, Patrizio Angelini, Ioannis. G. Tollis

Publication date: 15 January 2016

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1308.6706

zbMATH Keywords

algorithmsgraph drawingarea requirementgraph planaritycrossing complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Hierarchical partial planarity, Planarity of streamed graphs

Cites Work

• Unnamed Item
• Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
• A sufficient condition for the existence of plane spanning trees on geometric graphs
• Drawing graphs with right angle crossings
• How to draw a planar graph on a grid
• Strictly convex drawings of planar graphs
• Configurations with few crossings in topological graphs
• On the maximum number of edges in quasi-planar graphs
• On the maximum number of edges in topological graphs with no four pairwise crossing edges
• Graphs drawn with few crossings per edge
• The complexity of detecting crossingfree configurations in the plane
• On geometric graphs with no \(k\) pairwise parallel edges
• Drawing planar graphs using the canonical ordering
• Applications of the crossing number
• Density of straight-line 1-planar graph drawings
• Planarity of streamed graphs
• Advancements on SEFE and partitioned book embedding problems
• Area requirement of graph drawings with few crossings per edge
• The Crossing-Angle Resolution in Graph Drawing
• Fáry’s Theorem for 1-Planar Graphs
• Noncrossing Subgraphs in Topological Layouts
• Short path queries in planar graphs in constant time
• Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
• On the Density of Maximal 1-Planar Graphs
• Testing Maximal 1-Planarity of Graphs with a Rotation System in Linear Time
• Testing Simultaneous Planarity when the Common Graph is 2-Connected
• h-Quasi Planar Drawings of Bounded Treewidth Graphs in Linear Area
• The Number of Edges in $k$-Quasi-planar Graphs