Parameterized algorithms for beyond-planar crossing numbers

DOI10.4230/LIPICS.GD.2024.25MaRDI QIDQ6920456zbMATH OpenFDO

Authors Miriam Münch, Ignaz Rutter

Publication date 7 October 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.GD.2024.25

zbMATH Keywords

FPTbeyond-planaritycrossing patternscrossing-number

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 5485473 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A linear-time algorithm for testing outer-1-planarity
• A simpler proof of the excluded minor theorem for higher surfaces
• A subpolynomial approximation algorithm for graph crossing number in low-degree graphs
• Adding one edge to planar graphs makes crossing number and 1-planarity hard
• An improved algorithm for finding tree decompositions of small width
• Approximating the crossing number of graphs embeddable in any orientable surface
• Are crossings important for drawing large graphs?
• Beyond planar graphs. Communications of National Institute of Informatics (NII) Shonan meetings, Shonan, Japan, November 27 -- December 1, 2016
• Computing crossing numbers in quadratic time
• Crossing Number is NP-Complete
• Crossing Numbers and Parameterized Complexity
• Fan-crossing free graphs and their relationship to other beyond-planar graphs
• Fan-planarity: properties and complexity
• Gap-Planar Graphs
• Gap-planar graphs
• Graph Layout Aesthetics in UML Diagrams: User Preferences
• Graph minors. XIII: The disjoint paths problem
• Graphs drawn with few crossings per edge
• Min-\(k\)-planar drawings of graphs
• Min-k-planar drawings of graphs
• Minimal obstructions for 1-immersions and hardness of 1-planarity testing
• On fan-crossing graphs
• On the number of edges of fan-crossing free graphs
• On the relationship between \(k\)-planar and \(k\)-quasi-planar graphs
• Outer 1-planar graphs
• Parameterised partially-predrawn crossing number
• Parameterized complexity of 1-planarity
• Quasi-planar graphs have a linear number of edges
• Recognizing and embedding simple optimal 2-planar graphs
• Recognizing hole-free 4-map graphs in cubic time
• Recognizing optimal 1-planar graphs in linear time
• Simultaneous Embedding
• Star-struck by fixed embeddings: modern crossing number heuristics
• Testing gap \(k\)-planarity is NP-complete
• The density of fan-planar graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

This page was built for publication: Parameterized algorithms for beyond-planar crossing numbers

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