WWW.ABSTRACT.XLIBX.INFO
FREE ELECTRONIC LIBRARY - Abstract, dissertation, book
 
<< HOME
CONTACTS



Pages:   || 2 | 3 | 4 | 5 |   ...   | 7 |

«FARSHAD BARAHIMI Bachelor of Science, Shahid Bahonar University of Kerman, 2010 A Thesis Submitted to the School of Graduate Studies of the ...»

-- [ Page 1 ] --

WEB-BASED DRAWING SOFTWARE FOR GRAPHS IN 3D AND TWO LAYOUT

ALGORITHMS

FARSHAD BARAHIMI

Bachelor of Science, Shahid Bahonar University of Kerman, 2010

A Thesis

Submitted to the School of Graduate Studies

of the University of Lethbridge

in Partial Fulfillment of the

Requirements for the Degree

MASTER OF SCIENCE

Department of Mathematics and Computer Science University of Lethbridge

LETHBRIDGE, ALBERTA, CANADA

c Farshad Barahimi, 2015

WEB-BASED DRAWING SOFTWARE FOR GRAPHS IN 3D AND TWO LAYOUT

ALGORITHMS

FARSHAD BARAHIMI

Date of Defense: April 20, 2015 Dr. Stephen Wismath Supervisor Professor Ph.D.

Dr. Robert Benkoczi Thesis Examination Assistant Professor Ph.D.

Committee Member Dr. Joy Morris Thesis Examination Associate Professor Ph.D.

Committee Member Dr. Howard Cheng Chair, Associate Professor Ph.D.

Thesis Examination Committee Dedication Dedicated to my family whose value for me can not be expressed in words.

iii Abstract A new web-based software system for visualization and manipulation of graphs in 3D, named We3Graph is presented with a focus on accessibility, customizability for applications of graph drawing, usability and extendibility. The software system allows multiple users to work on the same graph at the same time and is accessible through web browsers.

The software can be extended using plugins written in any programming language and custom render engines written in the Javascript language. Also two new algorithms are

proposed to answer the following question, previously raised in [53]:

Given a graph G with n vertices, V = {v1, v2,..., vn }, and given a set of n distinct points P = {p1, p2,..., pn } each with integer coordinates in three dimensions, can G be drawn crossing-free on P with vi at pi and with a number of bends polynomial in n and in a volume polynomial in n and the dimension of P?

iv Acknowledgments I want to express my gratitude to Dr. Stephen Wismath for being a kind, experienced and professional supervisor whose support helped me a lot and I learned a lot from him. Also I want to express my special thanks to Dr. Howard Cheng, my coach in ACM ICPC programming contests. Also I want to express my gratitude to my great committee members, Dr. Robert Benkoczi and Dr. Joy Morris. I’m also grateful of my great friends for helping me during my master’s studies and life.

–  –  –

3.1 The user interface of Tulip, displaying a 5 vertex planar graph in the Node Link Diagram view............................... 37

3.2 The user interface of Cytoscape, displaying the E. coli interactome...... 39

3.3 The user interface of Gluskap, displaying a 3D drawing of the Peterson graph. 40

–  –  –

Introduction

1.1 Overview Graph visualization has many applications in software engineering, chemistry, bioinformatics, social sciences, information visualization, VLSI circuit design, etc. The academic efforts on graph drawing are usually separated into two categories. The first category is to determine algorithms to lay out graphs with respect to some criteria such as area, volume, number of crossings, symmetry, etc. The second category is to develop software systems that allow visualization and manipulation of graphs or implementation of layout algorithms.

Drawings of graphs are typically in two dimensions (2D) or three dimensions (3D).

While 2D graph drawing has been studied more, 3D graph drawing also looks promising as 3D technology is advancing and some applications of graph drawing have a 3D nature (such as protein structures).

A new web-based 3D graph visualization software package named We3Graph is developed as part of this dissertation with a focus on accessibility, customizability for applications of graph drawing, usability and extendibility. Also two new algorithms are proposed to answer a previously raised question in the 3D graph drawing literature.

1.2 Structure of this thesis

The rest of this chapter presents a high level system description and motivations of We3Graph as well as some background information. Chapter 2 reviews previous efforts on theoretical aspects of 3D graph drawing and also presents the new proposed algorithms.

Chapter 3 reviews previous efforts on graph drawing software. Chapter 4 talks about the software architecture and implementation of We3Graph. Chapter 5 concludes and discusses

1.4. WEB-BASED VISUALIZATION APPROACH possible paths for future work.

1.3 Applications of graph drawing First we give a brief overview of the applications of graph drawing. Graphs as a general model are used in many disciplines. Graph drawing adds geometrical properties to the graphs making it a more structured model. The 3D structure of chemistry molecules can be modelled as graphs in 3D space, in particular the 3D structure of some important biological molecules such as proteins can be modelled as graphs in 3D. Graph drawing is also used to visualize some important biological networks such as protein-protein interaction networks.





Different types of diagrams can be modelled as graphs by adding shape properties to vertices and adding bends to edges. The UML diagrams used in software engineering are a good example. Using graphs to visualize computer networks is another application of graph drawing. Social sciences use graphs to model social networks. Graph drawing is also used in VLSI circuit design. Different types of maps such as routes between cities can be modelled as graphs. The

Abstract

model of graphs has also different types such as directed or undirected graphs and graphs with multiple edges between two vertices. In some applications 2D drawings are used in practice but researchers are also studying 3D alternatives to 2D drawings [32, 51, 48, 63].

1.4 Web-based visualization approach

With the advent of WebGL in 2011, it is possible to build a web-based visualization tool for graphs in 3D. To be more precise, the graphs can be visualized and manipulated in a web browser and the World Wide Web can be used as a medium to communicate between different users and different pieces of the software.

In this dissertation we refer to traditional software systems as software systems that do not use web browsers for their interface and instead rely on a native user interface provided by the operating system. Some of the traditional software systems have a more offline na

<

1.4. WEB-BASED VISUALIZATION APPROACH

ture and depend solely on the computing and storage power of their host machine, while others have a more online nature and use mediums such as the World Wide Web communication protocols to access information from other resources and use computing and storage power of servers instead of the host machine.

Web-based software systems rely solely on the web browser for their user interface which increases the accessibility of the software. These software systems do not have any installation process and are also accessible through web browsers which are available on almost all platforms and devices such as computers, tablets, cell phones, windows, linux, mac, android, iOS, etc. We3Graph uses web browsers for its user interface to benefit from the above advantages but it is not designed for cell phones due to the restriction of their small display size. We3Graph also uses the World Wide Web communication protocols to communicate with the server. Graphs can be stored on the server, accessed from any location and shared among different users. Given the communication power of the World Wide Web, We3Graph provides a collaborative environment where multiple users can work on the same graph at the same time.

Although web-based software packages have the above benefits they suffer from lower performance and a less powerful user interface compared to traditional software, but the gap is closing as web technology is advancing with solutions like faster Javascript engines, HTML 5 and rich user interface libraries such as jQuery UI. Although in the first generation of web-based software systems, user interaction was very basic and static and it was not comparable to traditional software systems, in the new generation of web-based software systems, the user interaction is more mature and dynamic and is close but not equal to traditional software systems.

In the rest of this section, we briefly describe a few tools which can help the development of web-based visualization software, and touch on how We3Graph makes use of them.

–  –  –

1.4.1 WebGL standard WebGL is a hardware accelerated 3D graphics standard for web browsers based on OpenGL ES. WebGL uses an HTML5 canvas element for rendering, and Javascript as the programming interface. Though the first ideas of WebGL came in 2006 by Vladimir Vuki´ evi´, Khronos Group released the first official version of WebGL in 2011. WebGL is cc currently supported in the latest desktop and mobile versions of Google Chrome, Mozilla Firefox, Microsoft Internet Explorer and Apple Safari. We3Graph uses WebGL indirectly through Three.js library described bellow.

1.4.2 HTML 5 standard(s)

HTML 5 is the newest version of HTML (Hypertext Markup Language) and sometimes is used as an umbrella term referring to the set of standards for web browsers that are suitable for the next generation of powerful web applications, even though those standards have separate official specifications. HTML 5 supports multimedia with the new audio and video elements, 2D graphics with the new canvas element and elements for scalable vector graphics (SVG) and 3D graphics with WebGL. It also provides new semantic tags such as header, article, section, footer and new types for form inputs such as email and URL.

Other notable standards are Web Storage, Indexed Database API, File API, Web Workers, WebSockets and GeoLocation. HTML 5 combined with Javascript and server side code can be an alternative solution to traditional software. We3Graph use the WebGL standard as well as canvas element for textures used in custom render engines of WeGraph.

1.4.3 Three.js Javascript 3D graphics API While WebGL provides a low level API for 3D web graphics, Three.js is a Javascript library that provides a higher level API around the WebGL API to make writing code for 3D web graphics easier. We3Graph uses Three.js instead of programming WebGL directly.

–  –  –

1.5 Extendibility with web services Web Services allow exchange of data between a server application and a client application with a behaviour similar to the client application calling a function on the server application. We3Graph uses a web service API as core communication between different components of the system. Using web services allows plugins to be written in any programming language and run on any computer. Chapter 4 discusses the software architecture and implementation issues of We3Graph in more detail.

1.6 User interaction

This section provides an overview of the We3Graph user interaction and typical workow of the program. In addition to typical mouse, keyboard and 2D display interaction methods, We3Graph provides other interaction methods such as stereoscopic 3D using a side by side method, Leap Motion hand tracking device and the Oculus Rift virtual reality headset. Also the We3Graph user interface is tuned for touch screens.

1.6.1 Stereoscopic 3D and the Oculus Rift

In stereoscopic 3D, two different images are sent to each eye which will help the brain in depth perception. There are different ways to produce 3D stereoscopic effect. Among them we can mention anaglyph method, alternate frame sequencing method, polarization method and side by side 3D method. In the side by side 3D method, the rendered frame is divided into two sections, one for the left eye, and one for the right eye. The displaying device such as a 3D projector or a 3D TV combined with the proper 3D glasses send appropriate images to each eye. Previous research [64, 65] has shown that stereoscopic and motion cues improve the performance of the user for tracing paths in graphs. The Oclulus Rift virtual reality headset provides both stereoscopic and motion cues. The head mounted display of the Oculus Rift, combines stereoscopic 3D with head tracking, providing an immersive user experience. While low resolution is a drawback of the Oculus Rift headset, the newer

1.6. USER INTERACTION

version (DK2) has a higher resolution than the older version (DK1). We3Graph provides support for the OculusRift to allow the user benefit from the advantages stereoscopic display coupled with motion cues of head tracking and also provides a different user experience with immersive virtual reality.

1.6.2 Leap Motion

Leap Motion is a small usb device that tracks the hands and fingers. It can provide information such as finger tip position and direction, or palm normal vector. The reported model of hands is not always correct and the reliability of the reported model varies in different hand gestures. We3Graph uses Leap Motion in combination with a keyboard to provide a more reliable user interface. We3Graph allows the user to use the palm normal vector to manipulate the camera and the index finger to point to the monitor by emulating mouse movement. While the natural behaviour of pointing with the index finger improves the user experience compared to the mouse, the lack of accuracy downgrades the user effectiveness compared to the mouse. Also the fatigue caused by holding the hand high, makes the Leap Motion more appropriate for short interactions than long interactions. The spatial mapping between the camera orientation and palm normal improves the user interaction for navigating the graph.

1.6.3 Typical workflow



Pages:   || 2 | 3 | 4 | 5 |   ...   | 7 |


Similar works:

«Amethyst Hill Nursery HYDRANGEA-Species & Cultivars **NOTE—MINIMUM ORDER REQUIRED Please see inside cover for minimum requirements. For smaller quantities please see Hydrangeas Plus® Catalog. We are growing over 300 varieties of hydrangeas. Please see listings on following pages for names and descriptions grouped by price. For a color display of most of these varieties please see our website at our mail order site at www.hydrangeasplus.com. With our permission, our customers may use all...»

«Jan Schneider, Bernd Parusel Bericht 2008 über Migration und Asyl der deutschen nationalen Kontaktstelle für das Europäische Migrationsnetzwerk (EMN) Deutsche Nationale EMN-Kontaktstelle Herausgeber: Bundesamt für Migration und Flüchtlinge Migrationsund Integrationsforschung 90343 Nürnberg Stand: Juli 2009 Inhaltsverzeichnis Zusammenfassung Einleitung 1 Politische Entwicklungen in der Bundesrepublik Deutschland 1.1 Allgemeine Struktur des politischen Systems und der Institutionen im...»

«Carson Tate Work Simply: Embracing the Power of Your Personal Productivity Style PORTFOLIO / PENGUIN Карсон Тейт Работай легко Индивидуальный подход к повышению продуктивности Перевод с английского Светланы Кировой Москва «Манн, Иванов и Фербер» Оглавление Вступление. Схема навигации по книге......................»

«IPP‐Arbeitspapiere  6    Holger Knothe   Anerkennungsverhältnisse und Bürgerschaftliches Engagement ISSN 1614-3159 Impressum: Knothe, Holger (2004). Anerkennungsverhältnisse und Bürgerschaftliches Engagement. IPP-Arbeitspapiere Nr. 6. München: IPP München. ISSN 1614-3159. Die IPP-Arbeitspapiere werden herausgegeben vom Institut für Praxisforschung und Projektberatung IPP München, Ringseisstraße 8, 80337 München. Sie erscheinen in unregelmäßigen Abständen und sind online...»

«Competitiveness and Premium Analysis/Center for Urban Studies 1 The Competitiveness and Premium Excessiveness of the Home and Auto Insurance Industries in the State of Michigan Prepared by the Center for Urban Studies, Wayne State University for the Michigan Office of Financial and Insurance Services Professor George Galster, PhD, Principal Investigator With Jason C. Booza, Kurt Metzger, Ruth Waite September 30, 2004 Competitiveness and Premium Analysis/Center for Urban Studies 2 Table of...»

«FP7-ICT-4-248458 Multilingual Ontologies for Networked Knowledge D5.2.4 Performance Evaluation and Usability Study v4 Project ref. no FP7-ICT-4-248458 Project acronym Monnet Start date of project (dur.) 01 March 2010 (36 Months) Document due Date 31 August 2012 (M30) Responsible for deliverable NUIG Reply to sean.oriain@deri.org Document status Final D5.2.4 Performance Evaluation & Usability Studies v4 Page 1 of 21 FP7-ICT-4-248458 Project reference no. FP7-ICT-4-248458 Project working name...»

«A fine cut gemstone of fe rs the f u l l a r r ay of nat u r e’s intricate be au t y, h igh l igh t e d b y th e sk i l l of the l a p i d a r y ’s a r t. GEMSTONES A crystal fragment from deep within the earth, a raw natural creation. No other treasure of the earth has inspired man’s desire to capture and possess its extraordinary beauty like a gemstone. The spell a gem casts over the imagination is so powerful, it has also inspired us to free its beauty from imperfection and to mold its...»

«Drummond, Peter John (2014) An analysis of toponyms and toponymic patterns in eight parishes of the upper Kelvin basin. PhD thesis. http://theses.gla.ac.uk/5270/ Copyright and moral rights for this thesis are retained by the author A copy can be downloaded for personal non-commercial research or study, without prior permission or charge This thesis cannot be reproduced or quoted extensively from without first obtaining permission in writing from the Author The content must not be changed in any...»

«Politische Parteien in Belarus als notwendiger Bestandteil der Zivilgesellschaft Seminardokumentation Minsk A u t o r e n: Alexander Feduta, Oleg Boguzkij, Wiktor Martinowitsch Diese Veröffentlichung stellt keine Meinungsäußerung der Friedrich-Ebert-Stiftung dar. Für die inhaltlichen Aussagen tragen die Autorinnen und Autoren die Verantwortung.Politische Parteien in Belarus als notwendiger Bestandteil der Zivilgesellschaft: Seminardokumentation / Autoren: Alexander Feduta, Oleg Boguzkij,...»

«Vol. 85 (1994) No. 1 ACTA PHYSICA POLONICA A Proceedings of the European Conference Physics of Magnetism 93, Poznań 1993 LIGHT SCATTERING INVESTIGATIONS OF MAGNETIC ANISOTROPIES IN ULTRATHIN EPITAXIAL Co FILMS B. HILLEBRANDS, P. KRAMS, J. FASSBENDER, C. MATHIEU, G. GÜNTHERODT 2. Physikalisches Institut, RWTH Aachen, 52056 Aachen, Germany R. JUNGBLUT AND M.T. JOHNSON Philips Research, P.O. Box 80000, 5600JA Eindhoven, The Netherlands Using Brillouin light scattering, the properties of...»

«® Parallels Panel Kundenhandbuch, Parallels Plesk Panel Parallels Plesk Panel 11.0 Copyright-Vermerk Parallels IP Holdings GmbH Weltweite Unternehmenszentrale Vordergasse 59 500 SW 39th Street, Suite 200 CH-Schaffhausen Renton, WA 98057 Schweiz USA Telefon: +41 526320 411 Telefon: +1 (425) 282 6400 Fax:+41 52672 2010 Fax:+1 (425) 282 6445 Hauptniederlassung EMEA Sales Hauptniederlassung APAC Sales Willy-Brandt-Platz 3 3 Anson Road, #36-01 81829 Munich, DE Springleaf Tower, 079909 Telefon: +49...»

«Modulhandbuch Informatik (B.Sc.) Sommersemester 2015 Langfassung Stand: 12.02.2015 Fakultät für Informatik KIT Universität des Landes Baden-Württemberg und www.kit.edu nationales Forschungszentrum in der Helmholtz-Gemeinschaft Herausgeber: Fakultät für Informatik Karlsruher Institut für Technologie (KIT) 76131 Karlsruhe www.informatik.kit.edu Foto: KIT Ansprechpartner: beratung-informatik@informatik.kit.edu INHALTSVERZEICHNIS INHALTSVERZEICHNIS Inhaltsverzeichnis 1 Studienplan –...»





 
<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.