Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00256
Minimizing the Number of Label Transitions Around a Nonseparating Vertex of a Planar Graph
Vol. 16, no. 2, pp. 225241, 2012. Regular paper.
Abstract We study the minimum number of label transitions around a given vertex v_{0} in a planar multigraph G,
in which the edges incident with v_{0} are labelled with integers 1, …, l, and the minimum is taken over all embeddings of G in the plane.
For a fixed number of labels, a lineartime fixedparameter tractable algorithm that computes the minimum number of label transitions
around v_{0} is presented.
If the number of labels is unconstrained, then
the problem of deciding whether the minimum number of label transitions is at most k
is NPcomplete.

Submitted: July 2011.
Reviewed: October 2011.
Revised: November 2011.
Reviewed: January 2012.
Revised: January 2012.
Accepted: January 2012.
Final: January 2012.
Published: January 2012.
Communicated by
Csaba D. Tóth

Journal Supporters
