Approximating the Crossing Number of Apex Graphs

DOI10.1007/978-3-642-00219-9_42MaRDI QIDQ3611879zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Markus Chimani, Petr Hliněný, Petra Mutzel

Publication date 3 March 2009

Published in Graph Drawing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-00219-9_42

zbMATH Keywords

apex graphcrossing numbervertex insertion

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• Vertex insertion approximates the crossing number of apex graphs
• On graph crossing number and edge planarization
• An algorithm for the graph crossing number problem

Cites work

• Crossing and Weighted Crossing Number of Near-Planar Graphs
• Graphs on surfaces
• Inserting a vertex into a planar graph
• Inserting an edge into a planar graph
• On the Crossing Number of Almost Planar Graphs

Cited in

(5)

• \(\mathcal{P}\)-apex graphs
• Face covers and the genus problem for apex graphs
• Inapproximability ratios for crossing number
• On graph crossing number and edge planarization
• Vertex insertion approximates the crossing number of apex graphs

This page was built for publication: Approximating the Crossing Number of Apex Graphs

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