Linear-time algorithms for problems on planar graphs with fixed disk dimension
The disk dimension of a planar graph G is the least number k for which G embeds in the plane minus k open disks, with every vertex on the boundary of some disk. Useful properties of graphs with a given disk dimension are derived, leading to an algorithm to obtain an outerplanar subgraph of a graph w...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | article |
| Published: |
2007
|
| Online Access: | http://hdl.handle.net/10725/2777 http://dx.doi.org/10.1016/j.ipl.2006.08.006 http://www.sciencedirect.com/science/article/pii/S0020019006002511 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|