Trimming of Graphs, with Application to Point Labeling

Thomas Erlebach, Torben Hagerup, Klaus Jansen +2

For $t,g>0$, a vertex-weighted graph of total weight $W$ is $(t,g)$-trimmable if it contains a vertex-induced subgraph of total weight at least $(1-1/t)W$ and with no simple path o…