Boundary Classes of Planar Graphs
Author:
- 1 March 2008
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 17 (2) , 287-295
Abstract
We analyse classes of planar graphs with respect to various properties such as polynomial-time solvability of thedominating setproblem or boundedness of the tree-width. A helpful tool to address this question is the notion of boundary classes. The main result of the paper is that for many important properties there are exactly two boundary classes of planar graphs.Keywords
This publication has 12 references indexed in Scilit:
- Rank-width and vertex-minorsJournal of Combinatorial Theory, Series B, 2005
- Diameter and Treewidth in Minor-Closed Graph Families, RevisitedAlgorithmica, 2004
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex DegreeSIAM Journal on Discrete Mathematics, 2004
- On easy and hard hereditary classes of graphs with respect to the independent set problemDiscrete Applied Mathematics, 2003
- Finding Maximum Induced Matchings in Subclasses of Claw-Free and P 5-Free Graphs, and in Graphs with Matching and Induced Matching of Equal Maximum SizeAlgorithmica, 2003
- On maximum induced matchings in bipartite graphsInformation Processing Letters, 2002
- Upper bounds to the clique width of graphsDiscrete Applied Mathematics, 2000
- Treewidth for graphs with small chordalityDiscrete Applied Mathematics, 1997
- Computing independent sets in graphs with large girthDiscrete Applied Mathematics, 1992
- Edge Dominating Sets in GraphsSIAM Journal on Applied Mathematics, 1980