Efficient Extraction of Multiple Kuratowski Subdivisions

DOI10.1007/978-3-540-77537-9_17zbMATH Open1137.68474OpenAlexW1595830044WikidataQ56092456 ScholiaQ56092456MaRDI QIDQ5452219FDOQ5452219

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

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

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)

Cites Work

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

Cited In (7)

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

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)