---
_id: '14888'
abstract:
- lang: eng
  text: 'A face in a curve arrangement is called popular if it is bounded by the same
    curve multiple times. Motivated by the automatic generation of curved nonogram
    puzzles, we investigate possibilities to eliminate the popular faces in an arrangement
    by inserting a single additional curve. This turns out to be NP-hard; however,
    it becomes tractable when the number of popular faces is small: We present a probabilistic
    FPT-approach in the number of popular faces.'
acknowledgement: 'This work was initiated at the 16th European Research Week on Geometric
  Graphs in Strobl in 2019. A.W. is supported by the Austrian Science Fund (FWF):
  W1230. S.T. has been funded by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT19035].
  A preliminary version of this work has been presented at the 38th European Workshop
  on Computational Geometry (EuroCG 2022) in Perugia [9]. A full version of this paper,
  which includes appendices but is otherwise identical, is available as a technical
  report [10].'
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Phoebe
  full_name: De Nooijer, Phoebe
  last_name: De Nooijer
- first_name: Soeren
  full_name: Terziadis, Soeren
  last_name: Terziadis
- first_name: Alexandra
  full_name: Weinberger, Alexandra
  last_name: Weinberger
- first_name: Zuzana
  full_name: Masárová, Zuzana
  id: 45CFE238-F248-11E8-B48F-1D18A9856A87
  last_name: Masárová
  orcid: 0000-0002-6660-1322
- first_name: Tamara
  full_name: Mchedlidze, Tamara
  last_name: Mchedlidze
- first_name: Maarten
  full_name: Löffler, Maarten
  last_name: Löffler
- first_name: Günter
  full_name: Rote, Günter
  last_name: Rote
citation:
  ama: 'De Nooijer P, Terziadis S, Weinberger A, et al. Removing popular faces in curve
    arrangements. In: <i>31st International Symposium on Graph Drawing and Network
    Visualization</i>. Vol 14466. Springer Nature; 2024:18-33. doi:<a href="https://doi.org/10.1007/978-3-031-49275-4_2">10.1007/978-3-031-49275-4_2</a>'
  apa: 'De Nooijer, P., Terziadis, S., Weinberger, A., Masárová, Z., Mchedlidze, T.,
    Löffler, M., &#38; Rote, G. (2024). Removing popular faces in curve arrangements.
    In <i>31st International Symposium on Graph Drawing and Network Visualization</i>
    (Vol. 14466, pp. 18–33). Isola delle Femmine, Palermo, Italy: Springer Nature.
    <a href="https://doi.org/10.1007/978-3-031-49275-4_2">https://doi.org/10.1007/978-3-031-49275-4_2</a>'
  chicago: De Nooijer, Phoebe, Soeren Terziadis, Alexandra Weinberger, Zuzana Masárová,
    Tamara Mchedlidze, Maarten Löffler, and Günter Rote. “Removing Popular Faces in Curve
    Arrangements.” In <i>31st International Symposium on Graph Drawing and Network
    Visualization</i>, 14466:18–33. Springer Nature, 2024. <a href="https://doi.org/10.1007/978-3-031-49275-4_2">https://doi.org/10.1007/978-3-031-49275-4_2</a>.
  ieee: P. De Nooijer <i>et al.</i>, “Removing popular faces in curve arrangements,”
    in <i>31st International Symposium on Graph Drawing and Network Visualization</i>,
    Isola delle Femmine, Palermo, Italy, 2024, vol. 14466, pp. 18–33.
  ista: 'De Nooijer P, Terziadis S, Weinberger A, Masárová Z, Mchedlidze T, Löffler
    M, Rote G. 2024. Removing popular faces in curve arrangements. 31st International
    Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network
    Visualization, LNCS, vol. 14466, 18–33.'
  mla: De Nooijer, Phoebe, et al. “Removing Popular Faces in Curve Arrangements.”
    <i>31st International Symposium on Graph Drawing and Network Visualization</i>,
    vol. 14466, Springer Nature, 2024, pp. 18–33, doi:<a href="https://doi.org/10.1007/978-3-031-49275-4_2">10.1007/978-3-031-49275-4_2</a>.
  short: P. De Nooijer, S. Terziadis, A. Weinberger, Z. Masárová, T. Mchedlidze, M.
    Löffler, G. Rote, in:, 31st International Symposium on Graph Drawing and Network
    Visualization, Springer Nature, 2024, pp. 18–33.
conference:
  end_date: 2023-09-22
  location: Isola delle Femmine, Palermo, Italy
  name: 'GD: Graph Drawing and Network Visualization'
  start_date: 2023-09-20
date_created: 2024-01-28T23:01:43Z
date_published: 2024-01-06T00:00:00Z
date_updated: 2025-07-21T07:28:03Z
day: '06'
department:
- _id: UlWa
- _id: HeEd
doi: 10.1007/978-3-031-49275-4_2
external_id:
  arxiv:
  - '2202.12175'
intvolume: '     14466'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2202.12175
month: '01'
oa: 1
oa_version: Preprint
page: 18-33
project:
- _id: bdb2a702-d553-11ed-ba76-f12e3e5a3bc6
  grant_number: '101087907'
  name: 'A quantum hybrid of atoms and milligram-scale pendulums: towards gravitational
    quantum mechanics'
publication: 31st International Symposium on Graph Drawing and Network Visualization
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783031492747'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Removing popular faces in curve arrangements
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14466
year: '2024'
...