Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/24602
- Maximum order of planar digraphs
- We consider the degree/diameter problem for directed planar graphs. We show that planar digraphs with diameter 2 and maximum out-degree and in-degree d, d >= 41, cannot have more than 2d vertices. We show that 2d is the best possible upper bound by constructing planar digraphs of diameter 2 having exactly 2d vertices. Furthermore, we give upper and lower bounds for the largest possible order of planar digraphs with diameter greater than 2.
- Combinatorial Geometry and Graph Theory: Indonesia-Japan Joint Conference, IJCCGGT 2003 Bandung, Indonesia, September 13-16, 2003. Revised Selected Papers. (Bandung, Indonesia September 13-16, 2003)
- Springer Verlag
- Resource Type
- conference paper