Recognizing IC-planar and NIC-planar graphs

DOI10.7155/JGAA.00466zbMATH Open1388.05044arXiv1610.08884OpenAlexW2964181874WikidataQ129869104 ScholiaQ129869104MaRDI QIDQ4566013FDOQ4566013

Authors: Franz J. Brandenburg 

Publication date: 14 June 2018

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

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.

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

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

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)

Cites Work

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

Cited In (7)

• Title not available (Why is that?)
• \(\mathsf{NIC}\)-planar graphs
• An annotated bibliography on 1-planarity
• Recognizing and embedding simple optimal 2-planar graphs
• IC-planar graphs are 6-choosable
• Characterizing and recognizing 4-map graphs
• 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)