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

DOI10.1016/J.COMGEO.2015.07.002zbMATH Open1332.05099DBLPjournals/comgeo/AngeliniBLDGMPT15arXiv1308.6706OpenAlexW2160179167WikidataQ62046547 ScholiaQ62046547MaRDI QIDQ904086FDOQ904086

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

Publication date: 15 January 2016

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

Abstract: We initiate the study of the following problem: Given a non-planar graph G and a planar subgraph S of G, does there exist a straight-line drawing {Gamma} of G in the plane such that the edges of S are not crossed in {Gamma} by any edge of G? We give positive and negative results for different kinds of connected spanning subgraphs S of G. Moreover, in order to enlarge the subset of instances that admit a solution, we consider the possibility of bending the edges of G not in S; in this setting we discuss different trade-offs between the number of bends and the required drawing area.

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

Recommendations

• Drawing non-planar graphs with crossing-free subgraphs
• Large angle crossing drawings of planar graphs in subquadratic area
• Mathematical programs for drawing nonplanar graphs in the plane
• Area, curve complexity, and crossing resolution of non-planar graph drawings
• Area, curve complexity, and crossing resolution of non-planar graph drawings

zbMATH Keywords

algorithmsgraph drawingarea requirementgraph planaritycrossing complexity

Mathematics Subject Classification ID

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

Cites Work

• Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
• Graphs drawn with few crossings per edge
• How to draw a planar graph on a grid
• Density of straight-line 1-planar graph drawings
• Fáry's theorem for 1-planar graphs
• Title not available (Why is that?)
• On the density of maximal 1-planar graphs
• Area requirement of graph drawings with few crossings per edge
• The crossing-angle resolution in graph drawing
• The number of edges in \(k\)-quasi-planar graphs
• Drawing graphs with right angle crossings
• On the maximum number of edges in quasi-planar graphs
• Drawing planar graphs using the canonical ordering
• On geometric graphs with no \(k\) pairwise parallel edges
• Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
• \(h\)-quasi planar drawings of bounded treewidth graphs in linear area
• Testing maximal 1-planarity of graphs with a rotation system in linear time (extended abstract)
• On the maximum number of edges in topological graphs with no four pairwise crossing edges
• Applications of the crossing number
• Strictly convex drawings of planar graphs
• The complexity of detecting crossingfree configurations in the plane
• Short path queries in planar graphs in constant time
• Noncrossing Subgraphs in Topological Layouts
• A sufficient condition for the existence of plane spanning trees on geometric graphs
• Configurations with few crossings in topological graphs
• Planarity of streamed graphs
• Advancements on SEFE and partitioned book embedding problems
• Testing simultaneous planarity when the common graph is 2-connected

Cited In (8)

• Large angle crossing drawings of planar graphs in subquadratic area
• Hierarchical partial planarity
• Area, curve complexity, and crossing resolution of non-planar graph drawings
• Title not available (Why is that?)
• SOFSEM 2005: Theory and Practice of Computer Science
• Area, curve complexity, and crossing resolution of non-planar graph drawings
• Planarity of streamed graphs
• Drawing non-planar graphs with crossing-free subgraphs

This page was built for publication: Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q904086)