Resolving Popular Faces in Curve Arrangements

Abstract

In this thesis, we propose methods for resolving popular faces in curve arrangements by adding curves to the arrangement. A popular face is a face that is bordered by two or more edges that belong to the same curve. We introduce two algorithms that aim to resolve these popular faces. The first algorithm aims to resolve each popular face individually. The second algorithm aims to resolve these faces at once using a single curve. For this second algorithm, we use a path finding method introduced by Björklund et al. for returning a cycle that passes through a provided list of specified elements. This method runs in fixed parameter tractable time. Finally, we test both algorithms on a test set and perform a short comparative study on the results.