Graphs that admit right angle crossing drawings

DOI10.1016/J.COMGEO.2011.11.008MaRDI QIDQ419368zbMATH OpenOpenAlexWikidataFDO

Authors Karin Arikushi, Radoslav Fulek, Balázs Keszegh, Filip Morić, Csaba D. Tóth

Publication date 18 May 2012

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2011.11.008

zbMATH Keywords

Archimedean tilingcrossing lemmadischarginggraphpolyline drawingright angle crossing drawing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

The authors consider right angle crossing (RAC) drawings of graphs in which the edges are represented by polygonal arcs and any two edges can cross only at a right angle. It is shown that if a graph with \(n\) vertices admits a RAC drawing with at most \(1\) bend or \(2\) bends per edge, then the number of edges is at most \(6.5n\) and \(74.2n\), respectively.

Recommendations

• Graphs that admit right angle crossing drawings
• On the perspectives opened by right angle crossing drawings
• On the perspectives opened by right angle crossing drawings
• On RAC drawings of graphs with one bend per edge
• Drawing graphs with right angle crossings

Cites work

• Area, curve complexity, and crossing resolution of non-planar graph drawings
• Crossing-Free Subgraphs
• Drawing Graphs with Right Angle Crossings
• Improving the crossing lemma by finding more crossings in sparse graphs
• On the maximum number of edges in quasi-planar graphs
• On the perspectives opened by right angle crossing drawings
• On the size of graphs that admit polyline drawings with few bends and crossing angles

Cited in

(36)

• A heuristic approach towards drawings of graphs with high crossing resolution
• A greedy heuristic for crossing-angle maximization
• Right angle crossing graphs and 1-planarity
• RAC-drawability is \(\exists \mathbb{R} \)-complete
• On topological graphs with at most four crossings per edge
• Graphs that admit polyline drawings with few crossing angles
• Graphs that admit right angle crossing drawings
• On the size of graphs that admit polyline drawings with few bends and crossing angles
• The quality ratio of RAC drawings and planar drawings of planar graphs
• 2-layer right angle crossing drawings
• The straight-line RAC drawing problem is NP-hard
• Drawing Graphs with Right Angle Crossings
• Right angle crossing graphs and 1-planarity
• 2-layer right angle crossing drawings
• Large angle crossing drawings of planar graphs in subquadratic area
• Right Angle Crossing Drawings of Graphs
• The stub resolution of 1-planar graphs
• Every outer-1-plane graph has a right angle crossing drawing
• Notes on large angle crossing graphs
• scientific article; zbMATH DE number 7651192 (Why is no real title available?)
• On the perspectives opened by right angle crossing drawings
• On the perspectives opened by right angle crossing drawings
• On RAC drawings of graphs with one bend per edge
• On RAC drawings of graphs with one bend per edge
• scientific article; zbMATH DE number 7759289 (Why is no real title available?)
• RAC-Drawability is ∃ℝ-complete and Related Results
• On RAC drawings of graphs with two bends per edge
• Plane multigraphs with one-bend and circular-arc edges of a fixed angle
• On RAC drawings of graphs with two bends per edge
• Fixed-parameter algorithms for computing bend-restricted RAC drawings of graphs
• The density formula: one lemma to bound them all
• Drawing graphs with right angle crossings
• Edge densities of drawings of graphs with one forbidden cell
• Edge densities of drawings of graphs with one forbidden cell
• A characterization of complete bipartite RAC graphs
• RAC drawings in subcubic area

This page was built for publication: Graphs that admit right angle crossing drawings

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