Name
Abstract | ||
|---|---|---|
We study (deterministic) isolation for certain structures in directed and undirected planar graphs. The motivation for undertaking such a study comes from recent positive results on this topic. For example: Bourke et al. [2009] isolate a directed path in planar graphs and subsequently Datta et al. [2010b] isolate a perfect matching in bipartite planar graphs. Our first observation is that sufficiently strong (and plausible) isolations for certain structures in planar graphs would have strong consequences such as: NL ⊆ ⊕L, Bipartite-Matching ∈ NC, and NP ⊆ ⊕P. Our second observation is that although we do not yet have such strong isolations for arbitrary planar graphs, we do have them for bipartite planar graphs, that is, non-bipartiteness is the main bottleneck. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/2003685.2003687 | TOCT |
Keywords | Field | DocType |
certain structure,arbitrary planar graph,planar graphs,undirected planar graph,planar graph,perfect matching,recent positive result,main bottleneck,strong consequence,strong isolation,bipartite planar graph,bipartite matching,nc | Discrete mathematics,Combinatorics,Indifference graph,Robertson–Seymour theorem,Clique-sum,Chordal graph,Book embedding,Pathwidth,1-planar graph,Metric dimension,Mathematics | Journal |
Volume | Issue | Citations |
3 | 1 | 5 |
PageRank | References | Authors |
0.49 | 14 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Raghav Kulkarni | 1 | 172 | 19.48 |