Optimal 1-planar graphs which triangulate other surfaces

DOI10.1016/j.disc.2009.07.016zbMath1188.05056OpenAlexW2045737295MaRDI QIDQ1045136

Yusuke Suzuki

Publication date: 15 December 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2009.07.016

zbMATH Keywords

triangulationclosed surfaceoptimal 1-planar graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

An annotated bibliography on 1-planarity, \(\mathsf{NIC}\)-planar graphs, A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system, On morphing 1-planar drawings, On drawings and decompositions of 1-planar graphs, Right Angle Crossing Graphs and 1-Planarity, Relationship among triangulations, quadrangulations and optimal 1-planar graphs, Optimal 1-planar multigraphs, Right angle crossing graphs and 1-planarity, Unnamed Item, A linear-time algorithm for testing outer-1-planarity, Re-embedding a 1-plane graph for a straight-line drawing in linear time, On partitioning the edges of 1-plane graphs, Light subgraphs in the family of 1-planar graphs with high minimum degree, List edge and list total coloring of 1-planar graphs, Note on improper coloring of $1$-planar graphs, Generating polyhedral quadrangulations of the projective plane, Beyond Planar Graphs: Introduction, Algorithms for 1-Planar Graphs, Edge Partitions and Visibility Representations of 1-planar Graphs, $$\textit{\textbf{k}}$$-Planar Graphs, Fan-planarity: properties and complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Graphs that triangulate a given surface and quadrangulate another surface
• The structure of 1-planar graphs
• \(N\)-flips in even triangulations on the projective plane
• Constructing the graphs that triangulate both the torus and the Klein bottle
• Planar triangulations which quadrangulate other surfaces
• Ein Sechsfarbenproblem auf der Kugel
• \(N\)-flips in even triangulations on surfaces
• Panel structures of triangulations on the torus
• Generation of simple quadrangulations of the sphere
• Über 1-optimale Graphen
• Zur Struktur 1‐planarer Graphen
• N-flips in even triangulations on the sphere