Layout Embedding via Combinatorial Optimization

dc.contributor.authorBorn, Janisen_US
dc.contributor.authorSchmidt, Patricken_US
dc.contributor.authorKobbelt, Leifen_US
dc.contributor.editorMitra, Niloy and Viola, Ivanen_US
dc.date.accessioned2021-04-09T08:00:42Z
dc.date.available2021-04-09T08:00:42Z
dc.date.issued2021
dc.description.abstractWe consider the problem of injectively embedding a given graph connectivity (a layout) into a target surface. Starting from prescribed positions of layout vertices, the task is to embed all layout edges as intersection-free paths on the surface. Besides merely geometric choices (the shape of paths) this problem is especially challenging due to its topological degrees of freedom (how to route paths around layout vertices). The problem is typically addressed through a sequence of shortest path insertions, ordered by a greedy heuristic. Such insertion sequences are not guaranteed to be optimal: Early path insertions can potentially force later paths into unexpected homotopy classes. We show how common greedy methods can easily produce embeddings of dramatically bad quality, rendering such methods unsuitable for automatic processing pipelines. Instead, we strive to find the optimal order of insertions, i.e. the one that minimizes the total path length of the embedding. We demonstrate that, despite the vast combinatorial solution space, this problem can be effectively solved on simply-connected domains via a custom-tailored branch-and-bound strategy. This enables directly using the resulting embeddings in downstream applications which cannot recover from initializations in a wrong homotopy class. We demonstrate the robustness of our method on a shape dataset by embedding a common template layout per category, and show applications in quad meshing and inter-surface mapping.en_US
dc.description.number2
dc.description.sectionheadersMesh Generation
dc.description.seriesinformationComputer Graphics Forum
dc.description.volume40
dc.identifier.doi10.1111/cgf.142632
dc.identifier.issn1467-8659
dc.identifier.pages277-290
dc.identifier.urihttps://doi.org/10.1111/cgf.142632
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf142632
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectComputing methodologies
dc.subjectComputer graphics
dc.subjectMesh geometry models
dc.subjectMesh models
dc.titleLayout Embedding via Combinatorial Optimizationen_US
Files
Original bundle
Now showing 1 - 2 of 2
Loading...
Thumbnail Image
Name:
v40i2pp277-290.pdf
Size:
21.28 MB
Format:
Adobe Portable Document Format
Loading...
Thumbnail Image
Name:
cgf40-2_142632ProjektDeal.pdf
Size:
21.22 MB
Format:
Adobe Portable Document Format
Description:
Projekt Deal version
Collections