# Simultaneous Time-Space Upper Bounds for Certain Problems in Planar Graphs

Preprint · Diptarka Chakraborty, Raghunath Tewari

- Archive id: arxiv:1502.02135
- Published: 2015-02-07
- arXiv: https://arxiv.org/abs/1502.02135
- Source URL: https://arxiv.org/abs/1502.02135
- PDF: https://arxiv.org/pdf/1502.02135
- Provenance: arxiv

## Abstract

In this paper, we show that given a weighted, directed planar graph $G$, and any $ε\>0$, there exists a polynomial time and $O(n^{\\frac{1}{2}+ε})$ space algorithm that computes the shortest path between two fixed vertices in $G$. We also consider the {\\RB} problem, which states that given a graph $G$ whose edges are colored either red or blue and two fixed vertices $s$ and $t$ in $G$, is there a path from $s$ to $t$ in $G$ that alternates between red and blue edges. The {\\RB} problem in planar DAGs is {\\NL}-complete. We exhibit a polynomial time and $O(n^{\\frac{1}{2}+ε})$ space algorithm (for any $ε\>0$) for the {\\RB} problem in planar DAG. In the last part of this paper, we consider the problem of deciding and constructing the perfect matching present in a planar bipartite graph and also a similar problem which is to find a Hall-obstacle in a planar bipartite graph. We show the time-space bound of these two problems are same as the bound of shortest path problem in a directed planar graph.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.