Recognizing IC-planar and NIC-planar graphs

DOI10.7155/JGAA.00466MaRDI QIDQ4566013zbMATH OpenOpenAlexWikidataFDO

Authors Franz J. Brandenburg

Publication date 14 June 2018

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

IC-planar drawings

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: We prove that triangulated IC-planar and NIC-planar graphs can be recognized in cubic time. A graph is 1-planar if it can be drawn in the plane with at most one crossing per edge. A drawing is IC-planar if, in addition, each vertex is incident to at most one crossing edge and NIC-planar if two pairs of crossing edges share at most one vertex. In a triangulated drawing each face is a triangle. In consequence, planar-maximal and maximal IC-planar and NIC-planar graphs can be recognized in O(n^5) time and maximum and optimal ones in O(n^3) time. In contrast, recognizing 3-connected IC-planar and NIC-planar graphs is NP-complete, even if the graphs are given with a rotation system which describes the cyclic ordering of the edges at each vertex. Our results complement similar ones for 1-planar graphs.

Recommendations

• \(\mathsf{NIC}\)-planar graphs
• The coloring of the class of 1-planar graphs and its subclasses
• Recognizing optimal 1-planar graphs in linear time

Cites work

• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 3924797 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1518742 (Why is no real title available?)
• scientific article; zbMATH DE number 1775439 (Why is no real title available?)
• 1-planarity of graphs with a rotation system
• A linear-time algorithm for testing outer-1-planarity
• Adding one edge to planar graphs makes crossing number and 1-planarity hard
• Algorithms for graphs embeddable with few crossings per edge
• An annotated bibliography on 1-planarity
• Arboricity and Subgraph Listing Algorithms
• Chromatic number, independence ratio, and crossing number
• Coloring plane graphs with independent crossings
• Density of straight-line 1-planar graph drawings
• Drawing complete multipartite graphs on the plane with restrictions on crossings
• Drawing graphs. Methods and models
• Ein Sechsfarbenproblem auf der Kugel
• Enumeration of simple complete topological graphs
• Map graphs
• On the density of maximal 1-planar graphs
• Outer 1-planar graphs
• Parameterized complexity of 1-planarity
• Recognizing hole-free 4-map graphs in cubic time
• Recognizing optimal 1-planar graphs in linear time
• Rectilinear drawings of graphs
• Right angle crossing graphs and 1-planarity
• Straight-line grid drawings of 3-connected 1-planar graphs
• The structure of plane graphs with independent crossings and its applications to coloring problems
• Zur Struktur 1‐planarer Graphen
• \(\mathsf{NIC}\)-planar graphs
• Über 1-optimale Graphen

Cited in

(7)

• scientific article; zbMATH DE number 7559402 (Why is no real title available?)
• \(\mathsf{NIC}\)-planar graphs
• An annotated bibliography on 1-planarity
• Recognizing and embedding simple optimal 2-planar graphs
• Characterizing and recognizing 4-map graphs
• IC-planar graphs are 6-choosable
• On optimal beyond-planar graphs

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

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