Article

Appearance-preserving manipulation of hand-drawn graphs

Authors:

Kevin NovinsAuthors Info & Claims

GRAPHITE '05: Proceedings of the 3rd international conference on Computer graphics and interactive techniques in Australasia and South East Asia

Pages 61 - 68

https://doi.org/10.1145/1101389.1101400

Published: 29 November 2005 Publication History

Abstract

We describe a sketching system that allows users to create and manipulate directed graphs, such as those depicting state diagrams, using pen-input alone. The system exactly preserves the user's strokes, which may be entered in any order, and depicts them with a chalk texture to evoke a blackboard metaphor. The system automatically interprets the geometry of the sketch, distinguishing vertices, edges, and arrow heads, then tacitly imparts the intended graph semantics based on the two-dimensional placement of these elements. Once drawn, the user can manipulate the directed graph gesturally using the pen. The system responds to vertices or edges being picked and dragged by adjusting all adjacent edges appropriately. The original appearance of the hand-drawn vertices and edges is maintained even while their shapes are continually morphed in response to rearrangement of these elements. All edges exhibit shape memory, which is the proclivity to return to their original hand-drawn shape despite repeated stretching and compression.

References

[1]

Arvo, J., and Novins, K. 2000. Fluid sketches: Continuous recognition and morphing of simple hand-drawn shapes. In Proceedings of the 13th Annual ACM Symposium on User Interface Software and Technlogy.

Digital Library

[2]

Arvo, J., and Novins, K. 2000. Smart text: A synthesis of recognition and morphing. In AAAI Spring Symposium on Smart Graphics, 140--147.

[3]

Arvo, J., and Novins, K. 2006. Fluid sketching of directed graphs. In Proceedings of the Seventh Australasian User Interface Conference (AUIC2006). To Appear.

Digital Library

[4]

Arvo, J. 1999. Computer aided serendipity: The role of autonomous assistants in problem solving. In Proceedings of Graphics Interface '99, 183--192.

Digital Library

[5]

Blostein, D. 1996. General diagram-recognition methodologies. In Graphics Recognition: Methods and Applications, vol. 1072 of Lecture Notes in Computer Science. Springer-Verlag, New York, 106--122.

Digital Library

[6]

Di Battista, G., Eades, P., Tamassia, R., and Tollis, I. G. 1994. Algorithms for drawing graphs: an annotated bibliography. Computational Geometry: Theory and Applications 4, 5, 235--282.

Digital Library

[7]

Igarashi, T., Matsuoka, S., and Tanaka, H. 1999. Teddy: A sketching interface for 3d freeform design. In Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, 409--416.

Digital Library

[8]

Igarashi, T., Moscovich, T., and Hughes, J. F. 2005. As-rigid-as-possible shape manipulation. ACM Transactions on Graphics 24, 3, 1134--1141.

Digital Library

[9]

Julia, L., and Faure, C. 1995. Pattern recognition and beautification for a pen based interface. In ICDAR '95: Proceedings of the Third International Conference on Document Analysis and Recognition (Volume 1), IEEE Computer Society, Washington, DC, USA, 58--63.

Digital Library

[10]

Landay, J., and Meyers, B. 1995. Interactive sketching for the early stages of user interface design. In Proceedings of Computer-Human Interaction '95, 34--50.

Digital Library

[11]

LaViola, Jr., J. J., and Zeleznik, R. C. 2004. Mathpad2: a system for the creation and exploration of mathematical sketches. ACM Transactions on Graphics (TOG) archive 23, 3 (Aug.), 432--440.

Digital Library

[12]

Lewis, H. R., and Papadimitiou, C. H. 1981. Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, New Jersey.

Digital Library

[13]

Northrup, J. D., and Markosian, L. 2000. Artistic silhouettes: a hybrid approach. In NPAR '00: Proceedings of the 1st international symposium on Non-photorealistic animation and rendering, ACM Press, New York, NY, 31--37.

Digital Library

[14]

Plimmer, B., and Apperley, M. 2004. Interacting with sketched interface designs: an evaluation study. In CHI '04: CHI '04 extended abstracts on Human factors in computing systems, ACM Press, New York, NY, USA, 1337--1340.

Digital Library

[15]

Rubine, D. 1991. Specifying gestures by example. Computer Graphics 25, 4 (July), 329--337.

Digital Library

[16]

Smithies, S., Novins, K., and Arvo, J. 1999. A handwriting-based equation editor. In Proceedings of Graphics Interface '99, 84--91.

Digital Library

[17]

Stahovich, T. F. 1995. SketchIT: A Sketch Interpretation Tool for Conceptual Mechanical Design. PhD thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts.

Digital Library

[18]

Stahovich, T. F. 1998. The engineering sketch. IEEE Intelligent Systems 13, 3, 17--19.

[19]

Tolba, O., Dorsey, J., and McMillan, L. 1999. Sketching with projective 2d strokes. In Proceedings of the 12th Annual ACM Symposium on User Interface Software and Technlogy, 149--157.

Digital Library

[20]

Zanibbi, R., Novins, K., Arvo, J., and Zanibbi, K. 2001. Aiding manipulation of handwritten mathematical expressions through style-preserving morphs. In Proceedings of Graphics Interface 2001, 127--134.

Digital Library

[21]

Zeleznik, R. C., Herndon, K. P., and Hughes, J. F. 1996. SKETCH: An interface for gestural modeling. In Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, 163--170.

Digital Library

Cited By

Aksan EHilliges O(2021)Generative Ink: Data-Driven Computational Models for Digital InkArtificial Intelligence for Human Computer Interaction: A Modern Approach10.1007/978-3-030-82681-9_13(417-461)Online publication date: 5-Nov-2021
https://doi.org/10.1007/978-3-030-82681-9_13
Aksan EPece FHilliges OMandryk RHancock MPerry MCox A(2018)DeepWritingProceedings of the 2018 CHI Conference on Human Factors in Computing Systems10.1145/3173574.3173779(1-14)Online publication date: 21-Apr-2018
https://dl.acm.org/doi/10.1145/3173574.3173779
Bresler MPrźša DHlaváăź V(2016)Online recognition of sketched arrow-connected diagramsInternational Journal on Document Analysis and Recognition10.1007/s10032-016-0269-z19:3(253-267)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1007/s10032-016-0269-z
Show More Cited By

Index Terms

Appearance-preserving manipulation of hand-drawn graphs
1. Computing methodologies
  1. Computer graphics
2. Human-centered computing
  1. Human computer interaction (HCI)

Recommendations

Equimatchable Graphs on Surfaces

A graph G is equimatchable if each matching in G is a subset of a maximum-size matching and it is factor critical if G-v has a perfect matching for each vertex v of G. It is known that any 2-connected equimatchable graph is either bipartite or factor ...
Comparability Graphs Among Cover-Incomparability Graphs
Algorithms and Discrete Applied Mathematics
Abstract
Comparability graphs and cover-incomparability graphs (C-I graphs) are two interesting classes of graphs from posets. Comparability graph of a poset $P = (V, \leq)$ is a graph with vertex set V and two vertices u and v are adjacent in V if u and v are ...
Collapsible graphs and Hamiltonian connectedness of line graphs

Thomassen conjectured that every 4-connected line graph is Hamiltonian. Chen and Lai [Z.-H. Chen, H.-J. Lai, Reduction techniques for super-Eulerian graphs and related topics-an update, in: Ku Tung-Hsin (Ed.), Combinatorics and Graph Theory, vol. 95, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GRAPHITE '05: Proceedings of the 3rd international conference on Computer graphics and interactive techniques in Australasia and South East Asia

November 2005

456 pages

ISBN:1595932011

DOI:10.1145/1101389

Conference Chair:
Geoff Wyvill
University of Otago
,
Program Chairs:
David Arnold
University of Brighton
,
Mark Billinghurst
HIT Lab New Zealand

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 November 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GRAPHITE05

Sponsor:

SIGGRAPH

GRAPHITE05: International Conference on Computer Graphics and Interactive Techniques in Australasia and South East Asia 2005

November 29 - December 2, 2005

Dunedin, New Zealand

Acceptance Rates

GRAPHITE '05 Paper Acceptance Rate 38 of 93 submissions, 41%;

Overall Acceptance Rate 124 of 241 submissions, 51%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
449
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Aksan EHilliges O(2021)Generative Ink: Data-Driven Computational Models for Digital InkArtificial Intelligence for Human Computer Interaction: A Modern Approach10.1007/978-3-030-82681-9_13(417-461)Online publication date: 5-Nov-2021
https://doi.org/10.1007/978-3-030-82681-9_13
Aksan EPece FHilliges OMandryk RHancock MPerry MCox A(2018)DeepWritingProceedings of the 2018 CHI Conference on Human Factors in Computing Systems10.1145/3173574.3173779(1-14)Online publication date: 21-Apr-2018
https://dl.acm.org/doi/10.1145/3173574.3173779
Bresler MPrźša DHlaváăź V(2016)Online recognition of sketched arrow-connected diagramsInternational Journal on Document Analysis and Recognition10.1007/s10032-016-0269-z19:3(253-267)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1007/s10032-016-0269-z
Plimmer BPurchase HYang HBrereton MViller SKraal B(2010)SketchNodeProceedings of the 22nd Conference of the Computer-Human Interaction Special Interest Group of Australia on Computer-Human Interaction10.1145/1952222.1952249(136-143)Online publication date: 22-Nov-2010
https://dl.acm.org/doi/10.1145/1952222.1952249
Brown WBaird L(2008)A non-trigonometric, pseudo area preserving, polyline smoothing algorithmJournal of Computing Sciences in Colleges10.5555/1352079.135208723:4(35-42)Online publication date: 1-Apr-2008
https://dl.acm.org/doi/10.5555/1352079.1352087
Freeman IPlimmer B(2007)Connector semantics for sketched diagram recognitionProceedings of the eight Australasian conference on User interface - Volume 6410.5555/1273714.1273726(71-78)Online publication date: 30-Jan-2007
https://dl.acm.org/doi/10.5555/1273714.1273726
Reid PHallett-Hook FPlimmer BPurchase HThomas BBillinghurst M(2007)Applying layout algorithms to hand-drawn graphsProceedings of the 19th Australasian conference on Computer-Human Interaction: Entertaining User Interfaces10.1145/1324892.1324933(203-206)Online publication date: 28-Nov-2007
https://dl.acm.org/doi/10.1145/1324892.1324933
Chik VPlimmer BHosking JThomas BBillinghurst M(2007)Intelligent mind-mappingProceedings of the 19th Australasian conference on Computer-Human Interaction: Entertaining User Interfaces10.1145/1324892.1324931(195-198)Online publication date: 28-Nov-2007
https://dl.acm.org/doi/10.1145/1324892.1324931
Arvo JNovins K(2006)Fluid sketching of directed graphsProceedings of the 7th Australasian User interface conference - Volume 5010.5555/1151758.1151768(81-86)Online publication date: 1-Jan-2006
https://dl.acm.org/doi/10.5555/1151758.1151768

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents