A planar hypotraceable graph is a hypotraceable graph that is also planar. A number of planar
hypotraceable graphs are illustrated above.
Using a theorem of Thomassen (1974), the Wiener-Araya graph on 42 vertices can be used to construct a planar hypotraceable graph on
162 vertices, smaller than the 186-vertex graph obtained from the 48-Zamfirescu
graph using Thomassen's construction. These graphs are implemented in the Wolfram Language as GraphData["PlanarHypohamiltonian",
162]
and GraphData["PlanarHypohamiltonian",
186],
respectively.
Jooyandeh et al. (2017) showed that there exist planar hypotraceable graphs
on 154 vertices, as well as on all vertex counts greater than or equal to 156.
Using the 70-node Araya-Wiener graph, a 340-node
cubic planar hypotraceable graph can be constructed (Araya and Wiener 2011).
Holton and Sheehan (1993) asked if there exists an integer such that a cubic planar hypotraceable graph exists for every
even integer ,
and Araya and Wiener (2011) settled the question with .
Araya, M. and Wiener, G. "On Cubic Planar Hypohamiltonian and Hypotraceable Graphs." Elec. J. Combin.18, 2001. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p85/.Bondy,
J. A. and Murty, U. S. R. Graph
Theory with Applications. New York: North Holland, pp. 61 and 239-240,
1976.Grotschel, M. "On the Monotone Symmetric Travelling Salesman
Problem: Hypohamiltonian/Hypotraceable Graphs and Facets." Math. Operations
Res.5, 285-292, 1980.Grünbaum, B. "Vertices Missed
by Longest Paths or Circuits." J. Combin. Th. A17, 31-38, 1974.Holton,
D. A. and Sheehan, J. The
Petersen Graph. Cambridge, England: Cambridge University Press, 1993.Jooyandeh,
M.; McKay, B. D.; Östergård, P. R. J.; Pettersson, V. H.;
and Zamfirescu, C. T. "Planar Hypohamiltonian Graphs on 40 Vertices."
J. Graph Th.84, 121-133, 2017.Kapoor, S. F.; Kronk,
H. V.; and Lick, D. R. "On Detours in Graphs." Canad. Math.
Bull.11, 195-201, 1968.Thomassen, C. "Hypohamiltonian
and Hypotraceable Graphs." Disc. Math.9, 91-96, 1974.Walter,
H. "Über die Nichtexistenz eines Knotenpunktes, durch den alle längsten
Wege eines Graphen gehen." J. Combin. Th.6, 1-6, 1969.Wiener,
G. and Araya, M. "The Ultimate Question." 20 Apr 2009. http://arxiv.org/abs/0904.3012.Wiener,
G. and Araya, M. "On Planar Hypotraceable Graphs." J. Graph Th.67,
55-68, 2011.
"PlanarHypohamiltonian",
162
]
and GraphData[
"PlanarHypohamiltonian",
186
],
respectively.
such that a cubic planar hypotraceable graph exists for every
even integer 
,
and Araya and Wiener (2011) settled the question with 
.
