Research Output 1968 2020

Filter
Article
2020

Balanced line separators of unit disk graphs

Carmi, P., Chiu, M. K., Katz, M. J., Korman, M., Okamoto, Y., van Renssen, A., Roeloffzen, M., Shiitada, T. & Smorodinsky, S., 1 Jan 2020, In : Computational Geometry: Theory and Applications. 86, 14 p., 101575

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
Unit Disk Graph
Separator
Separators
Line
Half-plane

GPGPU linear complexity t-SNE optimization

Pezzotti, N., Thijssen, J., Mordvintsev, A., Hollt, T., Lew, B. V., Lelieveldt, B. P. F., Eisemann, E. & Vilanova, A., 2020, In : IEEE Transactions on Visualization and Computer Graphics.

Research output: Contribution to journalArticleAcademic

Computational complexity
Tensors
Scalability
Tuning
Textures
2019

Advanced light-field refocusing through tomographic modeling of the photographed scene

Viganò, N., Gil, P. M., Herzog, C., de la Rochefoucauld, O., van Liere, R. & Batenburg, K. J., 1 Jun 2019, In : Optics Express. 27, 6, p. 7834-7856 23 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
formulations
photography
point spread functions
frequency response
artifacts

A stable graph layout algorithm for processes

Mennens, R. J. P., Scheepens, R. & Westenberg, M. A., 1 Jan 2019, In : Computer Graphics Forum. 38, 3, p. 725-737 13 p.

Research output: Contribution to journalArticleAcademicpeer-review

Visualization
Industry
Animation
Semantics

ChronoCorrelator: enriching events with time series

van Dortmont, M. A. M. M., van den Elzen, S. & van Wijk, J. J., 10 Jul 2019, In : Computer Graphics Forum. 38, 3, p. 387-399 13 p.

Research output: Contribution to journalArticleAcademicpeer-review

Time series
Visualization
Servers
Health
Monitoring

Computing the chromatic number using graph decompositions via matrix rank

Jansen, B. M. P. & Nederlof, J., 7 Aug 2019, In : Theoretical Computer Science. 795, p. 520-539 20 p.

Research output: Contribution to journalArticleAcademicpeer-review

Graph Decomposition
Chromatic number
Decomposition
Computing
Graph in graph theory

Covering many points with a small-area box

de Berg, M. T., Cabello, S., Cheong, O., Eppstein, D. & Knauer, C., 2019, In : Journal of Computational Geometry. 10, 1, p. 207-222 16 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Covering
Rectangle
Cover
Linear Time
Integer

Dynamic conflict-free colorings in the plane

de Berg, M. & Markovic, A., 1 Jun 2019, In : Computational Geometry. 78, p. 61-73

Research output: Contribution to journalArticleAcademicpeer-review

Coloring
Colouring
Insertion
Color
Deletion

Dynamic graph coloring

Barba, L., Cardinal, J., Korman, M., Langerman, S., van Renssen, A., Roeloffzen, M. & Verdonschot, S., Apr 2019, In : Algorithmica. 81, 4, p. 1319-1341 23 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Dynamic Graphs
Graph Coloring
Coloring
Colouring
Update
3 Citations (Scopus)

Effects of environment knowledge in evacuation scenarios involving fire and smoke: a multiscale modelling and simulation approach

Richardson, O., Jalba, A. & Muntean, A., Mar 2019, In : Fire Technology. 55, 2, p. 415-436 22 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Smoke
Fires
Macros
Geometry

Efficient and accurate collision response for elastically deformable models

Verschoor, M. & Jalba, A. C., 1 Apr 2019, In : ACM Transactions on Graphics. 38, 2, 20 p., 17

Research output: Contribution to journalArticleAcademicpeer-review

Lagrange multipliers
Friction

Efficient optimal overlap removal: algorithms and experiments

Meulemans, W., 10 Jul 2019, In : Computer Graphics Forum. 38, 3, p. 713-723 11 p.

Research output: Contribution to journalArticleAcademicpeer-review

Diamonds
Computational complexity
Experiments

Faster DBScan and HDBScan in low-dimensional Euclidean spaces

de Berg, M., Gunawan, A. & Roeloffzen, M., 1 Mar 2019, In : International Journal of Computational Geometry and Applications. 29, 1, p. 21-47 27 p.

Research output: Contribution to journalArticleAcademicpeer-review

Euclidean space
Scale Parameter
Randomized Algorithms
Clustering Methods
Linear Time

Fully-dynamic and kinetic conflict-free coloring of intervals with respect to points

de Berg, M. T., Leijsen, T., Markovic, A., van Renssen, A., Roeloffzen, M. & Woeginger, G. J., 1 Mar 2019, In : International Journal of Computational Geometry and Applications. 29, 1, p. 49-72 24 p.

Research output: Contribution to journalArticleAcademicpeer-review

Coloring
Colouring
Kinetics
Color
Interval

Locally correct Fréchet matchings

Buchin, K., Buchin, M., Meulemans, W. & Speckmann, B., 1 Jan 2019, In : Computational Geometry. 76, p. 1-18 18 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
Curve
Monotone
Metric

Lower bounds for protrusion replacement by counting equivalence classes

Jansen, B. M. P. & Wulms, J. J. H. M., 5 Mar 2019, (Accepted/In press) In : Discrete Applied Mathematics.

Research output: Contribution to journalArticleAcademicpeer-review

Equivalence classes
Equivalence class
Replacement
Counting
Lower bound

Minimum perimeter-sum partitions in the plane

Abrahamsen, M., de Berg, M., Buchin, K., Mehr, M. & Mehrabi, A. D., 1 Jan 2019, In : Discrete and Computational Geometry. 23 p.

Research output: Contribution to journalArticleAcademicpeer-review

Perimeter
Partition
Approximation algorithms
Exact Algorithms
Pi

Non-crossing paths with geographic constraints

Silveira, R. I., Speckmann, B. & Verbeek, K., 23 May 2019, In : Discrete Mathematics and Theoretical Computer Science. 21, 3, 13 p.

Research output: Contribution to journalArticleAcademic

Open Access
File
Polynomials
Path
Vertical
Line segment
Convex Hull

Non-monochromatic and conflict-free colorings on tree spaces and planar network spaces

Aronov, B., de Berg, M., Markovic, A. & Woeginger, G., 31 Oct 2019, In : Algorithmica.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
Coloring
Colouring
Color
Interval
Conflict

On exploring always-connected temporal graphs of small pathwidth

Bodlaender, H. L. & van der Zanden, T. C., 1 Feb 2019, In : Information Processing Letters. 142, p. 68-71 4 p.

Research output: Contribution to journalArticleAcademicpeer-review

Pathwidth
Computational complexity
Graph in graph theory
NP-complete problem

On the maximum weight minimal separator

Hanaka, T., Bodlaender, H. L., van der Zanden, T. C. & Ono, H., 23 Sep 2019, (Accepted/In press) In : Theoretical Computer Science.

Research output: Contribution to journalArticleAcademicpeer-review

Separator
Separators
Tree Decomposition
Proper subset
Treewidth

Packing plane spanning graphs with short edges in complete geometric graphs

Aichholzer, O., Hackl, T., Korman, M., Pilz, A., van Renssen, A., Roeloffzen, M., Rote, G. & Vogtenhuber, B., 1 Sep 2019, In : Computational Geometry. 82, p. 1-15 15 p.

Research output: Contribution to journalArticleAcademicpeer-review

Geometric Graphs
Complete Graph
Packing
Sensor networks
Graph in graph theory

Region-based approximation of probability distributions (for visibility between imprecise points among obstacles)

Buchin, K., Kostitsyna, I., Löffler, M. & Silveira, R. I., 1 Jul 2019, In : Algorithmica. 81, 7, p. 2682–2715

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Visibility
Probability distributions
Probability density function
Probability Distribution
Polygon

RegressionExplorer: Interactive exploration of logistic regression models with subgroup analysis

Dingen, D., van 't Veer, M., Houthuizen, P., Mestrom, E. H. J., Korsten, E. H. H. M., Bouwman, A. R. A. & van Wijk, J., 1 Jan 2019, In : IEEE Transactions on Visualization and Computer Graphics. 25, 1, p. 246-255 10 p.

Research output: Contribution to journalArticleAcademicpeer-review

Logistics

Removing depth-order cycles among triangles: an algorithm generating triangular fragments

de Berg, M., 23 May 2019, In : Discrete and Computational Geometry.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
Triangular
Triangle
Fragment
Cycle
Computer graphics

Shortcuts for the circle

Bae, S. W., de Berg, M., Cheong, O., Gudmundsson, J. & Levcopoulos, C., 1 Feb 2019, In : Computational Geometry. 79, p. 37-54 18 p.

Research output: Contribution to journalArticleAcademicpeer-review

Circle
Plane Graph
Augmentation
Graph in graph theory
Unit circle

SolarView: low distortion radial embeddings with a focus

Castermans, T., Verbeek, K., Speckmann, B., Westenberg, M. A., Koopman, R., Wang, S., van den Berg, H. & Betti, A., Oct 2019, In : IEEE Transactions on Visualization and Computer Graphics. 25, 10, p. 2969-2982 14 p.

Research output: Contribution to journalArticleAcademicpeer-review

Solar system
Visualization
Systems analysis

Stability analysis of kinetic orientation-based shape descriptors

Meulemans, W., Verbeek, K. & Wulms, J., 27 Mar 2019, In : arXiv. 18 p., ArXiv:1903.11445v1

Research output: Contribution to journalArticleAcademic

Open Access
File
Kinetics
Costs
2 Citations (Scopus)

The complexity of Dominating set in geometric intersection graphs

de Berg, M., Kisfaludi-Bak, S. & Woeginger, G., May 2019, In : Theoretical Computer Science. 769, p. 18-31 14 p.

Research output: Contribution to journalArticleAcademicpeer-review

Geometric Graphs
Intersection Graphs
Dominating Set
Interval
Semi-algebraic Sets

The homogeneous broadcast problem in narrow and wide strips I: algorithms

de Berg, M., Bodlaender, H. L. & Kisfaludi-Bak, S., Jul 2019, In : Algorithmica. 81, 7, p. 2934-2962 29 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Broadcast
Strip
Wireless networks
Hardness
Polynomials
1 Citation (Scopus)

The homogeneous broadcast problem in narrow and wide strips II: lower bounds

de Berg, M., Bodlaender, H. L. & Kisfaludi-Bak, S., Jul 2019, In : Algorithmica. 81, 7, p. 2963-2990 28 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Broadcast
Strip
Computational complexity
Wireless networks
Lower bound

Turing kernelization for finding long paths in graph classes excluding a topological minor

Jansen, B. M. P., Pilipczuk, M. & Wrochna, M., 1 Oct 2019, In : Algorithmica. 81, 10, p. 3936-3967 32 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Kernelization
Longest Path
Graph Classes
Turing
Minor
1 Citation (Scopus)

Visual exploration of migration patterns in gull data

Konzack, M., Gijsbers, P., Timmers, F., van Loon, E., Westenberg, M. A. & Buchin, K., 1 Jan 2019, In : Information Visualization. 18, 1, p. 138-152 15 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Ecology
Animals
Trajectories
Statistics

Volume-based large dynamic graph analysis supported by evolution provenance

Bruder, V., Ben Lahmar, H., Hlawatsch, M., Frey, S., Burch, M., Weiskopf, D., Herschel, M. & Ertl, T., 29 Jun 2019, In : Multimedia Tools and Applications.

Research output: Contribution to journalArticleAcademicpeer-review

Visualization
Volume rendering
Scalability
Agglomeration
Graphics processing unit
2018

A faster parameterized algorithm for PSEUDOFOREST DELETION

Bodlaender, H. L., Ono, H. & Otachi, Y., 19 Feb 2018, In : Discrete Applied Mathematics. 236, p. 42-56

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Parameterized Algorithms
Fast Algorithm
Polynomials
Connected Components
Graph in graph theory

An efficient algorithm for the 1D total visibility-index problem and its parallelization

Afshani, P., de Berg, M., Casanova, H., Karsin, B., Lambrechts, C., Sitchinava, N. & Tsirogiannis, C., 1 Aug 2018, In : Journal on Experimental Algorithmics. 23, 2, 23 p., 2.3

Research output: Contribution to journalArticleAcademicpeer-review

Visibility
Parallelization
Efficient Algorithms
Line segment
Intersection

An optimal algorithm to compute the inverse beacon attraction region

Kostitsyna, I., Kouhestani, B., Langerman, S. & Rappaport, D., 15 Mar 2018, In : arXiv. 14 p., 1803.05946v1

Research output: Contribution to journalArticleAcademic

Open Access
File
Trees (mathematics)
Robotics
Trajectories

Approximating $(k,\ell)$-center clustering for curves

Buchin, K., Driemel, A., Gudmundsson, J., Horton, M., Kostitsyna, I., Löffler, M. & Struijs, M., 3 May 2018, In : arXiv. 24 p., 1805.01547v2

Research output: Contribution to journalArticleAcademic

Open Access
File
Clustering
Curve
Center Problem
Simplification
Approximation

Approximation and kernelization for chordal vertex deletion

Jansen, B. M. P. & Pilipczuk, M., 10 Jul 2018, In : SIAM Journal on Discrete Mathematics. 32, 3, p. 2258-2301 44 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Kernelization
Deletion
Approximation
Vertex of a graph
Chordal Graphs
1 Citation (Scopus)

Colored spanning graphs for set visualization

Hurtado, F., Korman, M., van Kreveld, M. J., Löffler, M., Sacristán, V., Shioura, A., Silveira, R. I., Speckmann, B. & Tokuyama, T., 1 Mar 2018, In : Computational Geometry. 68, p. 262-276 15 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Approximation algorithms
Ink
Visualization
Polynomials
Graph in graph theory

Computing nonsimple polygons of minimum perimeter

Fekete, S. P., Haas, A., Hemmer, M., Hoffmann, M., Kostitsyna, I., Krupke, D., Maurer, F., Mitchell, J. S. B., Schmidt, A., Schmidt, C. & Troegel, J., 2018, In : Journal of Computational Geometry. 8, 1, p. 340-365 26 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Perimeter
Travelling salesman problems
Polygon
Computing
Curve Reconstruction

Computing the similarity between moving curves

Buchin, K., Ophelders, T. & Speckmann, B., Aug 2018, In : Computational Geometry. 73, p. 2-14 13 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Curve
Computing
Similarity Measure
Polynomials
Polynomial time

Convex hull formation for programmable matter

Daymude, J. J., Gmyr, R., Hinnenthal, K., Kostitsyna, I., Scheideler, C. & Richa, A. W., 16 May 2018, In : arXiv. 25 p., 1805.06149v1

Research output: Contribution to journalArticleAcademic

Open Access
File
Seals

Convex partial transversals of planar regions

Keikha, V., Kerkhof, M. V. D., Kreveld, M. V., Kostitsyna, I., Löffler, M., Staals, F., Urhausen, J., Vermeulen, J. L. & Wiratma, L., 26 Sep 2018, In : arXiv. 29 p., 1809.10078v1

Research output: Contribution to journalArticleAcademic

Transversals
Partial
Line segment
Disjoint
Intersect
1 Citation (Scopus)

Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity

Bodlaender, H. L., Ono, H. & Otachi, Y., 2018, In : Algorithmica. 80, 7, p. 2160-2180

Research output: Contribution to journalArticleAcademicpeer-review

Parameterized Complexity
Graph Classes
Clique-width
Polynomials
Graph in graph theory

Drawing planar graphs with few geometric primitives

Hültenschmidt, G., Kindermann, P., Meulemans, W. & Schulz, A., 2018, In : Journal of Graph Algorithms and Applications. 22, 2, p. 357-387 31 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Line segment
Planar graph
Grid
Polynomials
Straight Line
1 Citation (Scopus)

Exact algorithms for terrain guarding

Ashok, P., Fomin, F. V., Kolay, S., Saurabh, S. & Zehavi, M., 1 Jun 2018, In : ACM Transactions on Algorithms. 14, 2, 20 p., 25

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Exact Algorithms
Approximation Algorithms
Parameterized Complexity
Line segment
Set of points

Exact and fixed parameter tractable algorithms for max-conflict-free coloring in hypergraphs

Ashok, P., Dudeja, A., Kolay, S. & Saurabh, S., 1 Jan 2018, In : SIAM Journal on Discrete Mathematics. 32, 2, p. 1189-1208 20 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Fixed-parameter Algorithms
Hypergraph
Colouring
Exact Algorithms
Parameterized Algorithms
11 Citations (Scopus)

Exploring multivariate event sequences using rules, aggregations, and selections

Cappers, B. C. M. & van Wijk, J. J., 1 Jan 2018, In : IEEE Transactions on Visualization and Computer Graphics. 24, 1, p. 532-541 10 p., 8019837

Research output: Contribution to journalArticleAcademicpeer-review

Structural analysis
Telecommunication traffic
Telecommunication
Servers
Agglomeration

Fast dynamic programming on graph decompositions

van Rooij, J. M. M., Bodlaender, H. L., Leeuwen, E. J. V., Rossmanith, P. & Vatshelle, M., 5 Jun 2018, In : arXiv. 2018, 54 p., 1806.01667

Research output: Contribution to journalArticleAcademic

Open Access
File
Graph Decomposition
Dynamic Programming
Dominating Set
Clique
Decompose