2023/12/25 by Franz J. Brandenburg, Brandenburg, Franz J.
Computer Science · #05C62 #68R10 #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2312.15793
openalex publication_date 2023/12/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is well-known that every 3-connected planar graph has a unique planar embedding on the sphere. We study the extension to triangulated 1-planar graphs, T1P graphs for short, which admit an embedding in which each edge is crossed at most once and each face is a triangle, and obtain an algorithmic solution by a cubic time recognition algorithm that also counts the number of T1P embeddings. In particular, we show that every triangulated planar graph has a unique T1P embedding, although it may admit many 1-planar embeddings, and that any 6-connected T1P graph has a unique 1-planar embedding, except for full generalized two-stars that admit two or eight 1-planar embeddings. Our algorithm extends, refines, and corrects a previous recognition algorithm by Chen, Grigni and Papadimitiou (``Recognizing Hole-Free 4-Map Graphs in Cubic Time'', Algorithmica 45 (2006)).