Planar oriented graphs of diameter two

S. Bau; P. Dankelmann; Michael A. Henning

Planar oriented graphs of diameter two

S. Bau, P. Dankelmann, Michael A. Henning

Research output: Contribution to journal › Article › peer-review

Abstract

Chvátal and Thomassen (J. Combinatorial Theory Ser. B 24 (1978) 61-75) proved that, given a 2-edge-connected graph G., the problem of deciding whether G has an orientation of diameter 2 is NP-complete. In this note we show that this problem, if restricted to planar graphs, becomes simple. We show that only two planar graphs admit a strong orientation of diameter 2: the 3-cycle and the octahedron.

Original language	English
Pages (from-to)	71-80
Number of pages	10
Journal	Utilitas Mathematica
Volume	79
Publication status	Published - Jul 2009
Externally published	Yes

Keywords

Diameter
Planar graph
Strong orientation

ASJC Scopus subject areas

Statistics and Probability
Statistics, Probability and Uncertainty
Applied Mathematics

Cite this

@article{9f61209f7a30453cacc87ce7ac4b2f0d,

title = "Planar oriented graphs of diameter two",

abstract = "Chv{\'a}tal and Thomassen (J. Combinatorial Theory Ser. B 24 (1978) 61-75) proved that, given a 2-edge-connected graph G., the problem of deciding whether G has an orientation of diameter 2 is NP-complete. In this note we show that this problem, if restricted to planar graphs, becomes simple. We show that only two planar graphs admit a strong orientation of diameter 2: the 3-cycle and the octahedron.",

keywords = "Diameter, Planar graph, Strong orientation",

author = "S. Bau and P. Dankelmann and Henning, {Michael A.}",

year = "2009",

month = jul,

language = "English",

volume = "79",

pages = "71--80",

journal = "Utilitas Mathematica",

issn = "0315-3681",

publisher = "Utilitas Mathematica Publishing Inc.",

}

TY - JOUR

T1 - Planar oriented graphs of diameter two

AU - Bau, S.

AU - Dankelmann, P.

AU - Henning, Michael A.

PY - 2009/7

Y1 - 2009/7

N2 - Chvátal and Thomassen (J. Combinatorial Theory Ser. B 24 (1978) 61-75) proved that, given a 2-edge-connected graph G., the problem of deciding whether G has an orientation of diameter 2 is NP-complete. In this note we show that this problem, if restricted to planar graphs, becomes simple. We show that only two planar graphs admit a strong orientation of diameter 2: the 3-cycle and the octahedron.

AB - Chvátal and Thomassen (J. Combinatorial Theory Ser. B 24 (1978) 61-75) proved that, given a 2-edge-connected graph G., the problem of deciding whether G has an orientation of diameter 2 is NP-complete. In this note we show that this problem, if restricted to planar graphs, becomes simple. We show that only two planar graphs admit a strong orientation of diameter 2: the 3-cycle and the octahedron.

KW - Diameter

KW - Planar graph

KW - Strong orientation

UR - http://www.scopus.com/inward/record.url?scp=67949109521&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:67949109521

SN - 0315-3681

VL - 79

SP - 71

EP - 80

JO - Utilitas Mathematica

JF - Utilitas Mathematica

ER -

Planar oriented graphs of diameter two

Abstract

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this