Planar graph bipartization in linear time

DOI10.1016/j.dam.2007.08.013zbMath1163.05052OpenAlexW1991223992MaRDI QIDQ2482113

Nadia Hardy, Adrian Vetta, Samuel Fiorini, Bruce A. Reed

Publication date: 16 April 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.08.013

zbMATH Keywords

treewidthlinear time algorithmplanar graphodd cycle

Mathematics Subject Classification ID

Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal ⋮ Hitting Selected (Odd) Cycles ⋮ Graph Bipartization Problem with Applications to Via Minimization in VLSI Design ⋮ Unnamed Item ⋮ A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs ⋮ Faster graph bipartization ⋮ A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Finding odd cycle transversals.
• Graph minors. V. Excluding a planar graph
• Mangoes and blueberries
• Primal-dual approximation algorithms for feedback problems in planar graphs
• Quickly excluding a planar graph
• Edge-disjoint odd cycles in planar graphs.
• Easy problems for tree-decomposable graphs
• Efficient Planarity Testing
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• A Minimax Theorem for Directed Graphs
• Planar Separators
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Planar graph bipartization in linear time