The thickness of fan-planar graphs is at most three

DOI10.1007/978-3-031-22203-0_18MaRDI QIDQ6172200zbMATH OpenOpenAlexWikidataFDO

Authors Otfried Cheong, Maximilian Pfister, Lena Schlipf

Publication date 16 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

beyond planarityFan-planaritythickness

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We prove that in any strongly fan-planar drawing of a graph G the edges can be colored with at most three colors, such that no two edges of the same color cross. This implies that the thickness of strongly fan-planar graphs is at most three. If G is bipartite, then two colors suffice to color the edges in this way.

Cites work

• Beyond planar graphs: introduction
• Beyond-planarity: Turán-type results for non-planar bipartite graphs
• Determining the thickness of graphs is NP-hard
• Edge partitions of optimal 2-plane and 3-plane graphs
• Edge-Disjoint Spanning Trees of Finite Graphs
• Fan-planar graphs
• scientific article; zbMATH DE number 3195968 (Why is no real title available?)
• scientific article; zbMATH DE number 3199421 (Why is no real title available?)
• On Optimal 2- and 3-Planar Graphs
• On topological graphs with at most four crossings per edge
• Simplifying non-simple fan-planar drawings
• The density of fan-planar graphs
• THE THICKNESS OF AN ARBITRARY COMPLETE GRAPH
• The thickness of fan-planar graphs is at most three
• The thickness of graphs: A survey
• Thickness and coarseness of graphs
• Triangle-free intersection graphs of line segments with large chromatic number

Cited in

(3)

• The family of fan-planar graphs
• Shallow Minors, Graph Products, and Beyond-Planar Graphs
• The thickness of fan-planar graphs is at most three

This page was built for publication: The thickness of fan-planar graphs is at most three

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