Non-planar core reduction of graphs
type: Item
instance of: scholarly article
title: Non-planar core reduction of graphs
zbMATH Open document ID: 1176.05077
author: Markus Chimani
author: Carsten Gutwenger
published in: Discrete Mathematics
publication date: 2009-04-09T00:00:00Z
review text: An algorithm is presented for reducing the number of edges of a graph while keeping the four main non-planarity characteristics of the original graph; its crossing number, skewness, coarseness and thickness (three of which are known to yield NP-hard optimization problems). This is intended as a means of speeding up the computation of these characteristics for heuristics and exact algorithms whose computational complexity depends of the number of the edges of the graph. The authors claim the experimental average reduction of 45\% of the number of edges of the original graph. The results rely on the use of the SPQR-trees, representing the decomposition of \(2\)-connected graphs into triconnected components. The definition of the non-planar core using maximal planar \(2\)-components is followed by a pseudocode for computing the core for non-planar graphs. The algorithm is shown to be of linear time complexity and to preserve all the four above listed non-planarity characteristics. The paper concludes with a discussion of further possible improvements, and the results of tests performed on the benchmark family known as the Rome library.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 5542413
zbMATH Keywords: preprocessing
zbMATH Keywords: graph reduction
zbMATH Keywords: crossing number
zbMATH Keywords: skewness
zbMATH Keywords: coarseness
zbMATH Keywords: thickness
zbMATH Keywords: linear time complexity algorithm
reviewed by: Robert Jajcay
describes a project that uses: PIGALE
MaRDI profile type: Publication
full work available at URL: j.disc.2007.12.078
OpenAlex ID: W1976060438
cites work: THE THICKNESS OF AN ARBITRARY COMPLETE GRAPH
cites work: Q5566314
cites work: The Coarseness of the Complete Bipartite Graph
cites work: The Thickness of the Complete Graph
cites work: Q5732335
cites work: On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
cites work: A branch-and-cut approach to the crossing number problem
cites work: Graph Drawing
cites work: An $O(m\log n)$-Time Algorithm for the Maximal Planar Subgraph Problem
cites work: A Better Approximation Algorithm for Finding Planar Subgraphs
cites work: On the Minimum Cut of Planarizations
cites work: Experiments on Exact Crossing Minimization Using Column Generation
cites work: On Cotree-Critical and DFS Cotree-Critical Graphs
cites work: An experimental comparison of four graph drawing algorithms.
cites work: On-line maintenance of triconnected components with SPQR-trees
cites work: On-Line Planarity Testing
cites work: Q3663340
cites work: Analysis of heuristics for finding a maximum weight planar subgraph
cites work: Skewness of graphs with small cutsets
cites work: Crossing Number is NP-Complete
cites work: An efficient graph planarization two‐phase heuristic
cites work: Q4472293
cites work: Inserting an edge into a planar graph
cites work: Q5587734
cites work: A coarseness conjecture of Erdös
cites work: The Coarseness of the Complete Graph
cites work: Parallel concepts in graph theory
cites work: Efficient Planarity Testing
cites work: Dividing a Graph into Triconnected Components
cites work: Computing and Combinatorics
cites work: Maximum planar subgraphs and nice embeddings: Practical layout tools
cites work: Planarizing graphs---a survey and annotated bibliography
cites work: Q3866146
cites work: Determining the thickness of graphs is NP-hard
cites work: The thickness of graphs: A survey
cites work: Q5524326
cites work: Reduction tests for the prize-collecting Steiner problem
cites work: Additivity of the crossing number of graphs with connectivity 2
cites work: On a problem of P. Turan concerning graphs
DOI: 10.1016/J.DISC.2007.12.078
description: scientific article; zbMATH DE number 5542413