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

摘要

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.