Publication:290513

DOI10.1007/978-3-319-27261-0_25zbMath1342.68251DBLPjournals/tcs/BrandenburgDEKL16arXiv1509.00388OpenAlexW2248326503WikidataQ62042378 ScholiaQ62042378MaRDI QIDQ290513

Fabrizio Montecchiani, Giuseppe Liotta, William S. Evans, Walter Didimo, Philipp Kindermann, Franz-Josef Brandenburg

Publication date: 1 June 2016

Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: IC-planar graphs are those graphs that admit a drawing where no two crossed edges share an end-vertex and each edge is crossed at most once. They are a proper subfamily of the 1-planar graphs. Given an embedded IC-planar graph $G$ with $n$ vertices, we present an $O(n)$-time algorithm that computes a straight-line drawing of $G$ in quadratic area, and an $O(n^3)$-time algorithm that computes a straight-line drawing of $G$ with right-angle crossings in exponential area. Both these area requirements are worst-case optimal. We also show that it is NP-complete to test IC-planarity both in the general case and in the case in which a rotation system is fixed for the input graph. Furthermore, we describe a polynomial-time algorithm to test whether a set of matching edges can be added to a triangulated planar graph such that the resulting graph is IC-planar.

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

zbMATH Keywords

graph drawingNP-hardness1-planarityIC-planarityright angle crossings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Recognizing and drawing IC-planar graphs
• 2-layer right angle crossing drawings
• Drawing complete multipartite graphs on the plane with restrictions on crossings
• A linear-time algorithm for drawing a planar graph on a grid
• Drawing graphs with right angle crossings
• How to draw a planar graph on a grid
• On the maximum number of edges in quasi-planar graphs
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Graphs drawn with few crossings per edge
• Quasi-planar graphs have a linear number of edges
• Graph drawing software
• Empirical evaluation of aesthetics-based graph layout
• The structure of plane graphs with independent crossings and its applications to coloring problems
• Density of straight-line 1-planar graph drawings
• Right angle crossing graphs and 1-planarity
• Area requirement of graph drawings with few crossings per edge
• Ein Sechsfarbenproblem auf der Kugel
• Algorithms for graphs embeddable with few crossings per edge
• Parameterized Complexity of 1-Planarity
• The Crossing-Angle Resolution in Graph Drawing
• Straight-Line Grid Drawings of 3-Connected 1-Planar Graphs
• Fáry’s Theorem for 1-Planar Graphs
• Coloring plane graphs with independent crossings
• Topology-Driven Force-Directed Algorithms
• Crossing Number is NP-Complete
• Mining Graph Data
• Chromatic number, independence ratio, and crossing number
• Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
• Rectilinear drawings of graphs
• Graph Drawing and Applications for Software and Knowledge Engineers
• Computing crossing numbers in quadratic time
• 1-Planarity of Graphs with a Rotation System
• The Number of Edges in $k$-Quasi-planar Graphs
• Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
• Crossing Numbers and Parameterized Complexity
• Enumeration of simple complete topological graphs
• Drawing graphs. Methods and models

Related Items (39)

Recognizing and drawing IC-planar graphs ⋮ RAC-drawability is \(\exists \mathbb{R} \)-complete ⋮ Recognizing and embedding simple optimal 2-planar graphs ⋮ On fan-crossing and fan-crossing free graphs ⋮ Recognizing IC-Planar and NIC-Planar Graphs ⋮ On RAC drawings of 1-planar graphs ⋮ The Stub Resolution of 1-planar Graphs ⋮ Fan-crossing free graphs and their relationship to other beyond-planar graphs ⋮ An annotated bibliography on 1-planarity ⋮ \((k,p)\)-planarity: a relaxation of hybrid planarity ⋮ \(\mathsf{NIC}\)-planar graphs ⋮ On morphing 1-planar drawings ⋮ New results on edge partitions of 1-plane graphs ⋮ Weak-dynamic coloring of graphs beyond-planarity ⋮ Unnamed Item ⋮ L-visibility drawings of IC-planar graphs ⋮ RAC-Drawability is ∃ℝ-complete and Related Results ⋮ Recognizing optimal 1-planar graphs in linear time ⋮ \(\mathsf{T}\)-shape visibility representations of 1-planar graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Gap-Planar Graphs ⋮ A heuristic approach towards drawings of graphs with high crossing resolution ⋮ Efficient Generation of Different Topological Representations of Graphs Beyond-Planarity ⋮ 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 ⋮ Two-Planar Graphs Are Quasiplanar ⋮ Characterizing 5-map graphs by 2-fan-crossing 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 ⋮ Gap-planar graphs ⋮ On RAC drawings of graphs with one bend per edge ⋮ On Aligned Bar 1-Visibility Graphs ⋮ Improper odd coloring of IC-planar graphs ⋮ Edge Partitions and Visibility Representations of 1-planar Graphs ⋮ Right Angle Crossing Drawings of Graphs ⋮ IC-Planar Graphs Are 6-Choosable

This page was built for publication: Recognizing and drawing IC-planar graphs