Minimizing the Number of Label Transitions Around a Nonseparating Vertex of a Planar Graph

Abstract

We study the minimum number of label transitions around a given vertex v₀ in a planar multigraph G, in which the edges incident with v₀ 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 v₀ 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.