MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given an undirected graph $G$ (can be cyclic) with the promise that all its faces have $3$ sides, is it possible to find the minimum distance between a source and any other vertices in LogSpace or in LogDCFL, at least under the constraint that between any two vertices there are polynomially many paths?

share|cite|improve this question
@StefanKohl: Please limit the flood of minor edits to a handful per day. See . – Emil Jeřábek Oct 16 '15 at 15:42
@EmilJeřábek: o.k.. – Stefan Kohl Oct 16 '15 at 15:45
What do you mean by "all its faces have 3 sides"? Faces are not a concept that makes sense for arbitrary (non-planar) graphs. And when you say "between any two vertices there are polynomially many paths", you mean simple paths, right? But in an undirected graph that's still a very strong restriction. – David Eppstein Oct 17 '15 at 4:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.