Non-planar core reduction of graphs
| Autor: | Carsten Gutwenger, Markus Chimani |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
Discrete mathematics
SPQR tree Book embedding 1-planar graph law.invention Planar graph Theoretical Computer Science Combinatorics symbols.namesake Pathwidth law Outerplanar graph Line graph symbols Discrete Mathematics and Combinatorics Crossing number (graph theory) MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Discrete Mathematics. 309(7):1838-1855 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2007.12.078 |
| Popis: | We present a reduction method that reduces a graph to a smaller core graph which behaves invariant with respect to non-planarity measures like crossing number, skewness, coarseness, and thickness. The core reduction is based on the decomposition of a graph into its triconnected components and can be computed in linear time. It has applications in heuristic and exact optimization algorithms for the non-planarity measures mentioned above. Experimental results show that this strategy reduces the number of edges by 45% in average for a widely used benchmark set of graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect