Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00256 Minimizing the Number of Label Transitions Around a Nonseparating Vertex of a Planar Graph Bojan Mohar and Petr Škoda Vol. 16, no. 2, pp. 225-241, 2012. Regular paper Abstract We study the minimum number of label transitions around a given vertex v0 in a planar multigraph G, in which the edges incident with v0 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 linear-time fixed-parameter tractable algorithm that computes the minimum number of label transitions around v0 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 NP-complete.
|
Revised: January 2012. Revised: November 2011. Submitted: July 2011. Reviewed: January 2012. Accepted: January 2012. Reviewed: October 2011. Published: January 2012. Final: January 2012. Communicated by Csaba Tóth |
| Journal of Graph Algorithms and Applications |