Right angle crossing graphs and 1-planarity

DOI10.1016/j.dam.2012.11.019zbMath1408.05042OpenAlexW2122778940WikidataQ59702327 ScholiaQ59702327MaRDI QIDQ1949102

Peter Eades, Giuseppe Liotta

Publication date: 25 April 2013

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.11.019

zbMATH Keywords

1-planaritygeometric graph theoryRAC graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) 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) Graph operations (line graphs, products, etc.) (05C76)

Related Items (38)

The density of fan-planar graphs ⋮ Outer 1-planar graphs ⋮ Recognizing and drawing IC-planar graphs ⋮ On fan-crossing and fan-crossing free graphs ⋮ Recognizing IC-Planar and NIC-Planar Graphs ⋮ On RAC drawings of 1-planar graphs ⋮ Fan-crossing free graphs and their relationship to other beyond-planar graphs ⋮ An annotated bibliography on 1-planarity ⋮ On the recognition of fan-planar and maximal outer-fan-planar graphs ⋮ \(\mathsf{NIC}\)-planar graphs ⋮ Proper 1-immersions of graphs triangulating the plane ⋮ A note on 1-planar graphs ⋮ All 2-planar graphs having the same spanning subgraph ⋮ Unnamed Item ⋮ Recognizing optimal 1-planar graphs in linear time ⋮ \(\mathsf{T}\)-shape visibility representations of 1-planar graphs ⋮ Efficient generation of different topological representations of graphs beyond-planarity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles ⋮ A heuristic approach towards drawings of graphs with high crossing resolution ⋮ Efficient Generation of Different Topological Representations of Graphs Beyond-Planarity ⋮ Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large Angles ⋮ On partitioning the edges of 1-plane graphs ⋮ Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar ⋮ Embedding-preserving rectangle visibility representations of nonplanar graphs ⋮ Unnamed Item ⋮ On RAC drawings of graphs with one bend per edge ⋮ Compact drawings of 1-planar graphs with right-angle crossings and few bends ⋮ Ortho-polygon visibility representations of embedded graphs ⋮ On RAC drawings of graphs with one bend per edge ⋮ On Aligned Bar 1-Visibility Graphs ⋮ Planar graphs having no proper 2-immersions in the plane. I ⋮ Beyond Planar Graphs: Introduction ⋮ Right Angle Crossing Drawings of Graphs ⋮ 2-Layer k-Planar Graphs ⋮ Fan-planarity: properties and complexity ⋮ On the Number of Edges of Fan-Crossing Free Graphs

Cites Work

• 1-planarity of complete multipartite graphs
• Computing and combinatorics. 18th annual international conference, COCOON 2012, Sydney, Australia, August 20--22, 2012. Proceedings
• Area, curve complexity, and crossing resolution of non-planar graph drawings
• Drawing graphs with right angle crossings
• Bounds on the crossing resolution of complete geometric graphs
• A characterization of complete bipartite RAC graphs
• The structure of 1-planar graphs
• Optimal 1-planar graphs which triangulate other surfaces
• Graphs drawn with few crossings per edge
• Graph drawing software
• Empirical evaluation of aesthetics-based graph layout
• Minimal non-1-planar graphs
• The Crossing-Angle Resolution in Graph Drawing
• Geometric RAC Simultaneous Drawings of Graphs
• Fáry’s Theorem for 1-Planar Graphs
• Graphs that Admit Right Angle Crossing Drawings
• On the Size of Graphs That Admit Polyline Drawings with Few Bends and Crossing Angles
• Maximizing the Total Resolution of Graphs
• The Quality Ratio of RAC Drawings and Planar Drawings of Planar Graphs
• The Straight-Line RAC Drawing Problem Is NP-Hard
• 2-Layer Right Angle Crossing Drawings
• Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
• Rectilinear drawings of graphs
• Large Angle Crossing Drawings of Planar Graphs in Subquadratic Area
• On the Density of Maximal 1-Planar Graphs
• Testing Maximal 1-Planarity of Graphs with a Rotation System in Linear Time
• Notes on large angle crossing graphs
• On the Perspectives Opened by Right Angle Crossing Drawings
• Drawing graphs. Methods and models
• Acyclic colouring of 1-planar graphs

This page was built for publication: Right angle crossing graphs and 1-planarity