On Minimizing the Number of Label Transitions around a Vertex of a Planar Graph

摘要

We study the minimum number of label transitions around a given vertex v_o in a planar multigraph G in which the edges incident with v_o are labelled with integers 1,...,l, where the minimum is taken over all embeddings of G in the plane. For a fixed number of labels, a linear-time FPT algorithm that (given the labels around v_o) computes the minimum number of label transitions around v_o 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.