pith. sign in

arxiv: 1509.03447 · v1 · pith:NNYMERZQnew · submitted 2015-09-11 · 💻 cs.CG

On 4-Map Graphs and 1-Planar Graphs and their Recognition Problem

Franz J. Brandenburg This is my paper
classification 💻 cs.CG
keywords graphsplanarpolynomialrespectivelycorrespondencecrossing-augmenteddegreeestablish
0
0 comments X
read the original abstract

We establish a one-to-one correspondence between 1-planar graphs and general and hole-free 4-map graphs and show that 1-planar graphs can be recognized in polynomial time if they are crossing-augmented, fully triangulated, and maximal 1-planar, respectively, with a polynomial of degree 120, 3, and 5, respectively.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Min-1-Planarity is NP-Hard

    cs.CG 2026-05 unverdicted novelty 7.0

    Deciding if a graph admits a min-1-planar drawing is NP-hard.