ERATO 感謝祭 Season II
小関 健太(国立情報学研究所)(JST, ERATO, 河原林巨大グラフプロジェクト)
Joint work with河原林 健一 (NII & JST, ERATO)

Today’s topics
 Spanning closed walks and TSP in 3-connectedplanar graphs, JCTB 109 (2014) 1-33.
 4-connected projective-planar graphs are

hamiltonian-connected, JCTB 112 (2015) 36-69.
Journal of Combinatorial Theory Series B (JCTB)：組合せ論の雑誌，Series B は主にグラフ理論

4th August, 2015

ERATO 感謝祭 Season II2

Hamiltonian cycles
Hamiltonian cycles in GCycles passingvertices in G

4th August, 2015

ERATO 感謝祭 Season II3

Hamiltonian cyclesHamiltonian cycles in G

Cycles passing
vertices in G

4th August, 2015

ERATO 感謝祭 Season II

4

Hamiltonicity of plane graphs
Tait (1884) :cubic maps have Hamiltonian cycle

plane graphs have a 4-coloring True (4-color thm.)

4th August, 2015

ERATO 感謝祭 Season II

5

Hamiltonicity of plane graphs
Tait (1884) :cubic maps have Hamiltonian cycle

plane graphs have a 4-coloring True (4-color thm.)

4th August, 2015

ERATO 感謝祭 Season II

6

Hamiltonicity of plane graphs
Tait (1884) :cubic maps have Hamiltonian cycle

plane graphs have a 4-coloring True (4-color thm.)

4th August, 2015

ERATO 感謝祭 Season II

7

Hamiltonicity of plane graphs
Tait (1884) :cubic maps have Hamiltonian cycle

plane graphs have a 4-coloring True (4-color thm.)

4th August, 2015

ERATO 感謝祭 Season II

8

Hamiltonicity of plane graphs
Tait (1884) :cubic maps have Hamiltonian cycle

plane graphs have a 4-coloring True (4-color thm.)

4th August, 2015

ERATO 感謝祭 Season II

9Hamiltonicity of plane graphs
Tait (1884) :cubic maps have Hamiltonian cycle

plane graphs have a 4-coloring True (4-color thm.)

4th August, 2015

ERATO 感謝祭 Season II

10

Hamiltonicity of plane graphs
Tait (1884) :cubic maps have Hamiltonian cycle False

plane graphs have a 4-coloring True (4-color thm.)

4th August, 2015

ERATO 感謝祭 Season II

11

Hamiltonicity of plane graphs
Tait (1884) :cubic maps have Hamiltonian cycle False

plane graphs have a 4-coloring True (4-color thm.)
Other application
・TSP (Travelling Salesman Problem)
・VLSI (Very Large Scale Integration) layout

4th August, 2015

ERATO 感謝祭 Season II

12

Hamiltonian cycles
Theorem (Tutte, `56 )4-connected plane graph has a Hamiltonian cycle.
G : k-conn.

4th August, 2015

with
G – S is connected

ERATO 感謝祭 Season II

13

Hamiltonian cycles
Theorem (Tutte, `56 )4-connected plane graph has a Hamiltonian cycle.
G : k-conn.

with
G – S is connected

There still remain several interesting conjectures in this area.
 The 3-connected case (Goemans Conj.) The case of graphs on projective plane (Dean Conj.)

4th August, 2015

ERATO 感謝祭 Season II

14

Today’s topics
 Spanning closed walks and TSP in 3-connectedplanar graphs, JCTB 109 (2014) 1-33.
 4-connected projective-planar graphs are

hamiltonian-connected, JCTB 112 (2015) 36-69.
Journal of Combinatorial Theory Series B (JCTB)：組合せ論の雑誌，Series B は主にグラフ理論

4th August, 2015

ERATO 感謝祭 Season II

15

Hamiltonian cycles
Theorem (Tutte, `56 )4-connected plane graph has a Hamiltonian cycle.
Infinitely many 3-conn. non-Hamiltonian plane graph

4th August, 2015

ERATO 感謝祭 Season II

16

Hamiltonian cycles
Theorem (Tutte, `56 )4-connected plane graph has a Hamiltonian cycle.
Infinitely many 3-conn. non-Hamiltonian plane graph
ProblemFind ``good’’ structures which are close toHamiltonian cycles in 3-conn. plane graphs

4th August, 2015

ERATO 感謝祭 Season II

17

Hamiltonian cycles
Theorem (Tutte, `56 )4-connected plane graph has a Hamiltonian cycle.
Infinitely many 3-conn. non-Hamiltonian plane graph
ProblemFind ``good’’ structures which are close to
Hamiltonian cycles in 3-conn. plane graphs
Including plane triangulations
4th August, 2015

ERATO 感謝祭 Season II18

Hamiltonian cycles
Remark:2-conn. plane graphs
which are far from being HamiltonianEx. Complete bipartite graph
ProblemFind ``good’’ structures which are close toHamiltonian cycles in 3-conn. plane graphs
Including plane triangulations
4th August, 2015

ERATO 感謝祭 Season II19

Spanning closed walks
Here we focus on a spanning closed walk with short length.
SCW : Cycle which can pass thr. vertices many times
A Hamiltonian cycle = a SCW of length |G|

SCW of length 9
4th August, 2015

ERATO 感謝祭 Season II

20

Spanning closed walks
Here we focus on a spanning closed walk with short length.
SCW : Cycle which can pass thr. vertices many times
A Hamiltonian cycle = a SCW of length |G|
Thm. (Asano, Nishizeki, Watanabe, 1980)

Plane triangulation has
a SCW of length.

SCW of length 9
4th August, 2015

ERATO 感謝祭 Season II

21

Spanning closed walks
Here we focus on a spanning closed walk with short length.
SCW : Cycle which can pass thr. vertices many times
A Hamiltonian cycle = a SCW of length |G|
Thm. (Asano, Nishizeki, Watanabe, 1980)

Plane triangulation has
a SCW of length.

SCW of length 9
4th August, 2015

ERATO 感謝祭 Season II22

Spanning closed walks
Here we focus on a spanning closed walk with short length.
SCW : Cycle which can pass thr. vertices many times
A Hamiltonian cycle = a SCW of length |G|Thm. (Asano, Nishizeki, Watanabe, 1980)

Plane triangulation has
a SCW of length
Main Theorem

SCW of length 9
4th August, 2015

-time algorithm

3-conn. plane graph hasa SCW of length
ERATO 感謝祭 Season II.

.
23

Best possibility

H : Plane triangulation

4th August, 2015

ERATO 感謝祭 Season II24

Best possibility

H : Plane triangulation
G : Face subdivision of H
4th August, 2015

ERATO 感謝祭 Season II25

Best possibility

To span each added vertex,
we need the length

H : Plane triangulation
G : Face subdivision of H
4th August, 2015

ERATO 感謝祭 Season II26

Best possibility

To span each added vertex,
we need the length

For every SCW,
the length of it is

H : Plane triangulation
G : Face subdivision of H
4th August, 2015

ERATO 感謝祭 Season II27

GTSP for plane graphs
Graph-Traveling Salesman Problem (GTSP) :Input: a (undirected) graph G of order n
Want: a shortest Hamilton cycle of the complete graphwhere the weight of an edge is the distance in G

4th August, 2015

ERATO 感謝祭 Season II,

28

GTSP for plane graphs
Graph-Traveling Salesman Problem (GTSP) :Input: a (undirected) graph G of order n
Want: a shortest Hamilton cycle of the complete graphwhere the weight of an edge is the distance in G

GTSP
sub. tofor,: The set of edges
joining S andforfor

4th August, 2015

ERATO 感謝祭 Season II

29

GTSP for plane graphs
Graph-Traveling Salesman Problem (GTSP) :Input: a (undirected) graph G of order n
Want: a shortest Hamilton cycle of the complete graphwhere the weight of an edge is the distance in G

GTSP
sub. to4th August, 2015

for

: The set of edges
joining S andfor

SCW condition

forInteger restriction

ERATO 感謝祭 Season II,30

GTSP for plane graphs
4/3-Conjecture (Goemans ’95)

G : (connected) graph
OPT(GTSP)SER : Subtour Elimination Relaxation(Linear prog. relax. of GTSP)OPT(SER)

GTSP
sub. to4th August, 2015

for

: The set of edges
joining S andfor

SCW condition

forInteger restriction

ERATO 感謝祭 Season II31GTSP for plane graphs
4/3-Conjecture (Goemans ’95)

G : (connected) graph
OPT(GTSP)SER : Subtour Elimination Relaxation(Linear prog. relax. of GTSP)OPT(SER)``

3/2 ’’ is true for graph (Wolsey ’80, Shmoys, Williamson ‘90)
Remark:4th August, 2015

OPT(GTSP) = length of a shortest SCW in G,OPT(SER)

ERATO 感謝祭 Season II32GTSP for plane graphs
4/3-Conjecture (Goemans ’95)

G : (connected) graph
OPT(GTSP)SER : Subtour Elimination Relaxation(Linear prog. relax. of GTSP)OPT(SER)``

3/2 ’’ is true for graph (Wolsey ’80, Shmoys, Williamson ‘90)
Remark:OPT(GTSP) = length of a shortest SCW in G,
OPT(SER)
Conjectured by Goemans `07

Cor. of Main Thm.

4/3-Conjecture is true for 3-conn. plane graphs.
4th August, 2015

ERATO 感謝祭 Season II33

Today’s topics
 Spanning closed walks and TSP in 3-connectedplanar graphs, JCTB 109 (2014) 1-33.
 4-connected projective-planar graphs are

hamiltonian-connected, JCTB 112 (2015) 36-69.
Journal of Combinatorial Theory Series B (JCTB)：組合せ論の雑誌，Series B は主にグラフ理論

4th August, 2015

ERATO 感謝祭 Season II34

Hamiltonian-connected
G : Hamiltonian-conn.
For pair of vertices,H-path between themG : Hamiltonian-conn.

Hamilton cycle
Hamilton path
4th August, 2015

ERATO 感謝祭 Season II35

Hamiltonian-connected
G : Hamiltonian-conn.
For pair of vertices,H-path between themG : Hamiltonian-conn.

Hamilton cycle
Hamilton path
4th August, 2015

ERATO 感謝祭 Season II36

Surfaces
Plane

4th August, 2015

Proj. plane

Torus

K-bottle

ERATO 感謝祭 Season IIOthers374-connected graphs on surfaces
Plane

Proj. plane

H-pathH-cycleTorus

K-bottle

OthersThomas, Yu& Zang (‘05)

ThomasTutte (‘56) & Yu (‘94)

H-conn Thomassen(‘83)

4th August, 2015

ERATO 感謝祭 Season II38

4-connected graphs on surfaces
Plane

Proj. plane

H-pathH-cycleTorus

OthersK-bottle

Thomas, Yu& Zang (‘05)?

?

?
Grunbaum(‘70)?

Thomas
Tutte (‘56) & Yu (‘94) Nash-Williams(‘73)

H-conn Thomassen(‘83)

4th August, 2015?
Dean (‘90)

ERATO 感謝祭 Season II39

4-connected graphs on surfaces
Plane

Proj. plane

H-pathH-cycleTorus

OthersK-bottle

Thomas, Yu& Zang (‘05)?

?

?
Grunbaum(‘70)?

Thomas
Tutte (‘56) & Yu (‘94) Nash-Williams(‘73)

H-conn Thomassen(‘83)

4th August, 2015?
Dean (‘90)

ERATO 感謝祭 Season II40

4-conn. graphs on projective plane
Main Thm.

G : 4-connected graphs on the projective plane
Hamiltonian-connected
Projective plane

4th August, 2015

ERATO 感謝祭 Season II41

The view of Algorithm
Our proof implies the following-algorithm

Input : A 4-conn. Projective-planar graph G of order n
2 vertices x, y of G
Output : Hamilton path (Tutte path) in G between x, y

4th August, 2015

ERATO 感謝祭 Season II42

The view of Algorithm
Our proof implies the following-algorithm

Input : A 4-conn. Projective-planar graph G of order n
2 vertices x, y of G
Output : Hamilton path (Tutte path) in G between x, yChiba & Nishizeki (`89) :-time algorithm
to find Hamilton cycle in 4-conn. plane graph of order n
4th August, 2015

ERATO 感謝祭 Season II43

SummaryTheorem (Tutte, `56 )4-connected plane graph has a Hamilton cycle.
G : k-conn.

with
G – S is connected

There still remain several interesting conjectures in this area.
 The 3-connected case (Goemans Conj.) The case of graphs on projective plane (Dean Conj.)

4th August, 2015

ERATO 感謝祭 Season II44

Thank you for your attention