---
_id: '15012'
abstract:
- lang: eng
  text: We solve a problem of Dujmović and Wood (2007) by showing that a complete
    convex geometric graph on n vertices cannot be decomposed into fewer than n-1
    star-forests, each consisting of noncrossing edges. This bound is clearly tight.
    We also discuss similar questions for abstract graphs.
acknowledgement: János Pach’s Research partially supported by European Research Council
  (ERC), grant “GeoScape” No. 882971 and by the Hungarian Science Foundation (NKFIH),
  grant K-131529. Work by Morteza Saghafian is partially supported by the European
  Research Council (ERC), grant No. 788183, and by the Wittgenstein Prize, Austrian
  Science Fund (FWF), grant No. Z 342-N31.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: János
  full_name: Pach, János
  id: E62E3130-B088-11EA-B919-BF823C25FEA4
  last_name: Pach
- first_name: Morteza
  full_name: Saghafian, Morteza
  id: f86f7148-b140-11ec-9577-95435b8df824
  last_name: Saghafian
- first_name: Patrick
  full_name: Schnider, Patrick
  last_name: Schnider
citation:
  ama: 'Pach J, Saghafian M, Schnider P. Decomposition of geometric graphs into star-forests.
    In: <i>31st International Symposium on Graph Drawing and Network Visualization</i>.
    Vol 14465. Springer Nature; 2024:339-346. doi:<a href="https://doi.org/10.1007/978-3-031-49272-3_23">10.1007/978-3-031-49272-3_23</a>'
  apa: 'Pach, J., Saghafian, M., &#38; Schnider, P. (2024). Decomposition of geometric
    graphs into star-forests. In <i>31st International Symposium on Graph Drawing
    and Network Visualization</i> (Vol. 14465, pp. 339–346). Isola delle Femmine,
    Palermo, Italy: Springer Nature. <a href="https://doi.org/10.1007/978-3-031-49272-3_23">https://doi.org/10.1007/978-3-031-49272-3_23</a>'
  chicago: Pach, János, Morteza Saghafian, and Patrick Schnider. “Decomposition of Geometric
    Graphs into Star-Forests.” In <i>31st International Symposium on Graph Drawing
    and Network Visualization</i>, 14465:339–46. Springer Nature, 2024. <a href="https://doi.org/10.1007/978-3-031-49272-3_23">https://doi.org/10.1007/978-3-031-49272-3_23</a>.
  ieee: J. Pach, M. Saghafian, and P. Schnider, “Decomposition of geometric graphs
    into star-forests,” in <i>31st International Symposium on Graph Drawing and Network
    Visualization</i>, Isola delle Femmine, Palermo, Italy, 2024, vol. 14465, pp.
    339–346.
  ista: 'Pach J, Saghafian M, Schnider P. 2024. Decomposition of geometric graphs
    into star-forests. 31st International Symposium on Graph Drawing and Network Visualization.
    GD: Graph Drawing and Network Visualization, LNCS, vol. 14465, 339–346.'
  mla: Pach, János, et al. “Decomposition of Geometric Graphs into Star-Forests.”
    <i>31st International Symposium on Graph Drawing and Network Visualization</i>,
    vol. 14465, Springer Nature, 2024, pp. 339–46, doi:<a href="https://doi.org/10.1007/978-3-031-49272-3_23">10.1007/978-3-031-49272-3_23</a>.
  short: J. Pach, M. Saghafian, P. Schnider, in:, 31st International Symposium on
    Graph Drawing and Network Visualization, Springer Nature, 2024, pp. 339–346.
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-02-18T23:01:03Z
date_published: 2024-01-01T00:00:00Z
date_updated: 2026-04-16T09:12:37Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/978-3-031-49272-3_23
ec_funded: 1
external_id:
  arxiv:
  - '2306.13201'
  isi:
  - '001207939600023'
intvolume: '     14465'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2306.13201
month: '01'
oa: 1
oa_version: Preprint
page: 339-346
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '788183'
  name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z00342
  name: Mathematics, Computer Science
publication: 31st International Symposium on Graph Drawing and Network Visualization
publication_identifier:
  eisbn:
  - '9783031492723'
  eissn:
  - 1611-3349
  isbn:
  - '9783031492716'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '21253'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Decomposition of geometric graphs into star-forests
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 14465
year: '2024'
...