Graph drawing applications in combinatorial theory of maturity models
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929264046112768 |
|---|---|
| author | Kajzer, Špela Dobler, Alexander Jerebic, Janja Nöllenburg, Martin Orthaber, Joachim Bokal, Drago |
| author_facet | Kajzer, Špela Dobler, Alexander Jerebic, Janja Nöllenburg, Martin Orthaber, Joachim Bokal, Drago |
| contents | In this paper, we introduce tiled graphs as models of learning and maturing processes. We show how tiled graphs can combine graphs of learning spaces or antimatroids (partial hypercubes) and maturity models (total orders) to yield models of learning processes. For the visualization of these processes it is a natural approach to aim for certain optimal drawings. We show for most of the more detailed models that the drawing problems resulting from them are NP-complete. The terse model of a maturing process that ignores the details of learning, however, results in a polynomially solvable graph drawing problem. In addition, this model provides insight into the process by ordering the subjects at each test of their maturity. We investigate extremal and random instances of this problem, and provide exact results and bounds on their optimal crossing number.
Graph-theoretic models offer two approaches to the design of optimal maturity models given observed data: (1) minimizing intra-subject inconsistencies, which manifest as regressions of subjects, is modeled as the well-known feedback arc set problem. We study the alternative of (2) finding a maturity model by minimizing the inter-subject inconsistencies, which manifest as crossings in the respective drawing. We show this to be NP-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_02026 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Graph drawing applications in combinatorial theory of maturity models Kajzer, Špela Dobler, Alexander Jerebic, Janja Nöllenburg, Martin Orthaber, Joachim Bokal, Drago Discrete Mathematics In this paper, we introduce tiled graphs as models of learning and maturing processes. We show how tiled graphs can combine graphs of learning spaces or antimatroids (partial hypercubes) and maturity models (total orders) to yield models of learning processes. For the visualization of these processes it is a natural approach to aim for certain optimal drawings. We show for most of the more detailed models that the drawing problems resulting from them are NP-complete. The terse model of a maturing process that ignores the details of learning, however, results in a polynomially solvable graph drawing problem. In addition, this model provides insight into the process by ordering the subjects at each test of their maturity. We investigate extremal and random instances of this problem, and provide exact results and bounds on their optimal crossing number. Graph-theoretic models offer two approaches to the design of optimal maturity models given observed data: (1) minimizing intra-subject inconsistencies, which manifest as regressions of subjects, is modeled as the well-known feedback arc set problem. We study the alternative of (2) finding a maturity model by minimizing the inter-subject inconsistencies, which manifest as crossings in the respective drawing. We show this to be NP-complete. |
| title | Graph drawing applications in combinatorial theory of maturity models |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/2403.02026 |