Efficient Extraction of Multiple Kuratowski Subdivisions

DOI10.1007/978-3-540-77537-9_17MaRDI QIDQ5452219zbMATH OpenOpenAlexWikidataFDO

Authors Markus Chimani, Petra Mutzel, Jens M. Schmidt

Publication date 25 March 2008

Published in Graph Drawing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77537-9_17

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Classification and detection of obstructions to planarity
• Menus of kuratowski subgraphs
• A Planarity Test via Construction Sequences
• A new planarity test
• scientific article; zbMATH DE number 4079189

Cites work

• scientific article; zbMATH DE number 1305401 (Why is no real title available?)
• A characterization of planar graphs by Trémaux orders
• An experimental comparison of four graph drawing algorithms.
• Depth-First Search and Kuratowski Subgraphs
• Efficient Extraction of Multiple Kuratowski Subdivisions
• Efficient Planarity Testing
• Graph Drawing
• Maintenance of a minimum spanning forest in a dynamic plane graph
• Maximum planar subgraphs and nice embeddings: Practical layout tools
• On Cotree-Critical and DFS Cotree-Critical Graphs
• On the Cutting Edge: Simplified O(n) Planarity by Edge Addition

Cited in

(7)

• Computing Maximum C-Planar Subgraphs
• A note on the practicality of maximal planar subgraph algorithms
• A New Approach to Exact Crossing Minimization
• Menus of kuratowski subgraphs
• Exact algorithms for the maximum planar subgraph problem: new models and experiments
• Cycles to the rescue! Novel constraints to compute maximum planar subgraphs fast
• Efficient Extraction of Multiple Kuratowski Subdivisions

Describes a project that uses

Uses Software

• PIGALE

This page was built for publication: Efficient Extraction of Multiple Kuratowski Subdivisions

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