| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652349 | Electronic Notes in Discrete Mathematics | 2009 | 5 Pages |
Abstract
We consider the problem of minimizing the diameter of an orientation of a planar graph. A result of Chvátal and Thomassen shows that for general graphs, it is NP-complete to decide whether a graph can be oriented so that its diameter is at most two. In contrast to this, for each constant l, we describe an algorithm that decides if a planar graph G has an orientation with diameter at most l and runs in time O(c|V|), where c depends on l.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
