Paper Info
Title
Space Complexity of Optimization Problems in Planar Graphs.
Abstract
We initiate the study of space complexity of certain optimization problems restricted to planar graphs. We provide upper bounds and hardness results in space complexity for some of these well-studied problems in the context of planar graphs. In particular we show the following: 1. Max-Cut in planar graphs has a (UL boolean AND co - UL)-approximation scheme; 2. Sparsest-Cut in planar graphs is in NL; 3. Max-Cut in planar graphs is NL-hard; 4. circle plus Directed-Spanning-Trees in planar graphs is circle plus L-complete. For (1) we analyze the space complexity of the well known Baker's algorithm [1] using a recent result of Elberfeld, Jakoby, and Tantau [13] that gives a Log-space analogue of Courcelle's Theorem for MSO definable properties of bounded tree-width graphs. For (2) we analyze the space complexity of the algorithm of Patel [21] that builds on a useful weighting scheme for planar graphs. Interestingly, the same weighting scheme has been crucially used in the totally different context of isolation in planar graphs [4,7]. For ( 3) we use a recent result of Kulkarni [17], which shows that Min-wt-PM in planar graphs is NL-hard. For (4) we use the result by Datta, Kulkarni, Limaye, and Mahajan [8] that gives a reduction from the permanent in general graphs to planar graphs.
Year
DOI
Venue
2014
10.1007/978-3-319-06089-7_21
Lecture Notes in Computer Science
Field
DocType
Volume
Discrete mathematics,Indifference graph,Combinatorics,Computer science,Chordal graph,Clique-sum,Book embedding,Pathwidth,Longest path problem,Clique problem,Maximal independent set
Conference
8402
ISSN
Citations 
PageRank 
0302-9743
1
0.35
References 
Authors
22
2
Name
Order
Citations
PageRank
Samir Datta120019.82
Raghav Kulkarni217219.48