## Abstract

In a storyline visualization, we visualize a collection of inter- acting characters (e.g., in a movie, play, etc.) by x-monotone curves that converge for each interaction, and diverge otherwise. Given a storyline with n characters, we show tight lower and upper bounds on the number of crossings required in any storyline visualization for a restricted case. In particular, we show that if (1) each meeting consists of exactly two characters and (2) the meetings can be modeled as a tree, then we can always find a storyline visualization with O(n log n) crossings. Fur- thermore, we show that there exist storylines in this restricted case that require Ω(n log n) crossings. Lastly, we show that, in the general case, minimizing the number of crossings in a storyline visualization is fixed- parameter tractable, when parameterized on the number of characters k. Our algorithm runs in time (Formula presented.), where m is the number of meetings.

Original language | English |
---|---|

Title of host publication | Proc. 23rd International Symposium Graph Drawing and Network Visualization (GD) |

Editors | E. Di Giacomo , A. Lubiw |

Place of Publication | Dordrecht |

Publisher | Springer |

Pages | 192-198 |

Number of pages | 7 |

ISBN (Electronic) | 978-3-319-27261-0 |

ISBN (Print) | 978-3-319-27260-3 |

DOIs | |

Publication status | Published - 2015 |

Event | 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015) - California State University Northridge, Los Angeles, United States Duration: 24 Sept 2015 → 26 Sept 2015 Conference number: 23 http://www.csun.edu/gd2015/ |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 9411 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015) |
---|---|

Abbreviated title | GD 2015 |

Country/Territory | United States |

City | Los Angeles |

Period | 24/09/15 → 26/09/15 |

Internet address |